4.6.0 — Sliding Window: The Pattern

Recognition cue. The problem asks for the longest, shortest, or best contiguous stretch — a substring or a subarray — that satisfies some condition. The word contiguous is the tell. If the problem allows gaps it is a subsequence, and that is dynamic programming, not a window.

The move. Two indices that both only ever move forwards. O(n^2) becomes O(n).

The two shapes

Almost every window problem is one of these two, and knowing which one you are in before writing anything saves most of the confusion.

# A. LONGEST valid window — shrink WHILE INVALID, record AFTER
left = 0
for right in range(len(a)):
    add(a[right])
    while not valid():
        remove(a[left])
        left += 1
    best = max(best, right - left + 1)

# B. SHORTEST valid window — shrink WHILE VALID, record INSIDE
left = 0
for right in range(len(a)):
    add(a[right])
    while valid():
        best = min(best, right - left + 1)
        remove(a[left])
        left += 1

A third shape is the fixed-size window, where the length is given. There is no while at all — you add the character entering on the right and remove the one leaving on the left, in one step.

# C. FIXED size k
for right in range(len(a)):
    add(a[right])
    if right >= k:
        remove(a[right - k])
    if right >= k - 1:
        record()

Why it is linear

Both pointers only move forwards, and left never passes right. So across the whole run, left advances at most n times in total — not n times per iteration of the outer loop. A while inside a for is therefore O(n), not O(n^2).

This is the same amortized argument as 4.4.9 and the monotonic stack. You will be asked for it.

The precondition nobody states

A window only works if shrinking reliably makes the window more valid.

With non-negative numbers, removing an element cannot increase the sum, so shrinking always moves you towards validity. Allow negative numbers and that breaks — removing an element might make the sum larger — and the window technique silently gives wrong answers. The replacement is prefix sums with a hash map.

Check this before reaching for a window. It is the single most common way to apply the pattern to a problem it does not fit.

The six problems

#	Problem	The one insight
4.6.1	Best Time to Buy and Sell Stock ★	Carry the cheapest price seen so far
4.6.2	Longest Substring Without Repeating ★	Shrink until the duplicate is gone
4.6.3	Longest Repeating Character Replacement ★	Valid when length − maxCount ≤ k
4.6.4	Permutation in String	Fixed-size window, compare letter counts
4.6.5	Minimum Window Substring ★	Count distinct requirements still unmet
4.6.6	Sliding Window Maximum	A monotonic deque keeps only possible winners

★ marks the Blind 75 subset.

The traps on this pattern

Recording the answer in the wrong place. Longest problems record after the shrink loop; shortest problems record inside it. Mixing them up gives answers that are subtly wrong on some inputs and right on others.

Off-by-one in the window length. It is right - left + 1, because both ends are included.

Slicing strings inside the loop. s[left:right+1] is O(n) and turns a linear solution quadratic. Track index pairs and slice once at the end.

Using list.pop(0) as a queue. It is O(n) in Python. Use collections.deque. JavaScript's Array.shift() has the same issue.

Applying a window where shrinking does not help. See the precondition above.

What the interviewer will push on

"Why is this O(n) when there is a nested loop?" The left pointer only moves forwards and never passes right, so it advances at most n times overall.

"Substring or subsequence?" Windows only do contiguous. If gaps are allowed, it is a different technique.

"Your maxCount in the replacement problem is never decreased — is that a bug?" No, and the argument is on 4.6.3. This is asked almost every time.

"What breaks if the array contains negative numbers?" Shrinking no longer reliably helps, so the window is invalid as a technique. Use prefix sums with a hash map instead.

One thing to volunteer: say which of the two shapes you are using before you write code. "This is a shortest-valid-window problem, so I shrink while valid and record inside the loop."

Recall

• Windows solve contiguous longest and shortest problems. Subsequences with gaps are DP, not windows.
• Longest: shrink while invalid, record after. Shortest: shrink while valid, record inside. Fixed size: no while at all.
• Linear because both pointers only move forwards and left never passes right — at most n advances in total.
• Window length is right − left + 1.
• The precondition: shrinking must make the window more valid. Negative numbers break that and force prefix sums instead.
• Track index pairs rather than slicing substrings inside the loop, or the solution goes quadratic.
• For the maximum or minimum over a sliding range, use a monotonic deque — O(1) per step.

Next: 4.6.1 Best Time to Buy and Sell Stock — the simplest member, and the one that quietly introduces the idea behind dynamic programming.