Variable-Size Windows

The template

python

1def longest_valid(items):2    left = 03    best = 04    state = {}5 6    for right, value in enumerate(items):7        add(state, value)8 9        # 'while', not 'if': one arrival can force several departures.10        while not is_valid(state):11            remove(state, items[left])12            left += 113 14        best = max(best, right - left + 1)15 16    return best

Grow, then restore validity

Concept

Why this is linear

The nested loop looks quadratic, but the left edge only ever moves forward and can never pass the right edge. Across the whole run it advances at most n times in total, so the two loops together do O(n) work.

Keeping validity cheap

The window is only as fast as its validity test. Comparing two frequency maps every iteration is O(alphabet) per step and quietly ruins the complexity. Maintain a scalar instead.

python

1# Instead of comparing maps, count how many requirements are fully met.2if window[char] == need[char]:3    satisfied += 1        # only at the exact crossing point4...5if window[char] < need[char]:6    satisfied -= 1        # only when it drops below

A single integer replaces the comparison

Common mistakes

Using `if` instead of `while` to shrink.
Measuring the width as right - left, losing one element.
Recording the best while the window is still invalid.
Leaving zero counts in a frequency map, so a size check reports characters that are no longer present.

Can you recognise the pattern?

A question about the longest, shortest, or number of contiguous ranges meeting a condition.

Watch a variable window grow and shrink

Quick quiz

Sliding window

1What goes wrong if the shrink step uses `if` instead of `while`?

for right, value in enumerate(items):
    add(state, value)
    if not is_valid(state):     # should be 'while'
        remove(state, items[left])
        left += 1

Nothing — one removal is always enough

The window can stay invalid when one arrival requires several removals

The loop never terminates

The window shrinks too far

2Why is the variable window linear despite having a loop inside a loop?

The inner loop runs at most a constant number of times

The left edge only moves forward, so it advances at most n times in total

The window size is bounded

It is actually quadratic

3In a covering-window problem, when should the 'satisfied requirements' counter be incremented?

Every time a required character is added

Only when a character's count exactly reaches its requirement

Once, when the window first becomes valid

When the window shrinks

The template

Why this is linear

Keeping validity cheap

Common mistakes

Sliding window

Practise

You’ve reached the end

Search Tech Epitome

Search Tech Epitome

Variable-Size Windows

The template

Why this is linear

Keeping validity cheap

Common mistakes

Practise

You’ve reached the end