Lessons · Python · the sliding window

A window that grows and shrinks

Keep a start and an end over the same sequence. The end always moves forward; the start moves forward only when the window has broken a rule. The items between them are the window.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

It is the answer to almost every question about the best CONTIGUOUS run: the longest stretch without a repeat, the smallest stretch containing everything, the best sum of any k in a row.

How to think about it

Find the word 'contiguous', or a substring, or 'in a row'. Then name the rule the window must obey, advance the end one item at a time, and while the rule is broken, advance the start.

Worked example

def longest_run_without_repeat(text):

The classic shape.

    last_seen, start, best = {}, 0, 0

Where each character was last seen; the window start; the answer.

    for end, ch in enumerate(text):

The end moves forward, once per character, forever.

        if ch in last_seen and last_seen[ch] >= start:

The repeat is INSIDE the window.

            start = last_seen[ch] + 1

Jump the start past it. Never backwards.

        last_seen[ch] = end

        best = max(best, end - start + 1)

The window is end - start + 1 wide.

    return best

print(longest_run_without_repeat('abcabcbb'))

print(longest_run_without_repeat('bbbbb'))

print(longest_run_without_repeat(''))

Your turn

Shrink the window past the repeated character.

if ch in last_seen and last_seen[ch] >= start:
    start =  + 1

The trap

It looks like a nested loop and is not. Each end moves forward at most n times across the whole run, so the total is one pass, not n squared.

Practise the sliding window on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.