Sliding Window (Variable Size)

1. The signal

• “Longest / shortest subarray or substring such that …”
• “at most k …”, “no repeating …”, “containing all of …”
• A contiguous run whose validity you can test incrementally.

The word that matters is contiguous. If the answer can skip elements, this isn’t a window problem.

2. The template

int l = 0, best = 0;
for (int r = 0; r < n; r++) {
    add(a[r]);                                  // expand
    while (invalid()) { remove(a[l]); l++; }    // shrink
    best = max(best, r - l + 1);                // record
}

let l = 0, best = 0;
for (let r = 0; r < n; r++) {
  add(a[r]);
  while (invalid()) { remove(a[l]); l++; }
  best = Math.max(best, r - l + 1);
}

Only invalid() changes between problems. Learn this shape once and the six problems in week 2 become variations on a theme rather than six separate things to memorise:

3. Why it’s O(n)

l and r both only ever move right, and neither can move more than n times. So even though there’s a while inside a for, the total number of pointer moves is at most 2n.

This is the same amortised argument as Longest Consecutive Sequence, and the same one that justifies the monotonic stack in week 3. Being able to say it out loud is worth more than the template.

4. Complexity

O(n) time. Space is whatever the window bookkeeping needs — O(1) for a fixed alphabet count array, O(k) for a hash map of distinct elements in the window.

5. The two flavours: maximise vs minimise

This trips people up, so it’s worth being explicit.

Maximising (longest valid window): shrink only while invalid, and record after the shrink loop — at that point the window is valid and as large as it can be for this r.

Minimising (shortest valid window, e.g. Minimum Window Substring): shrink while valid, and record inside the shrink loop, before each removal. You’re trying to squeeze the window as small as it goes while it still qualifies.

Same skeleton, inverted condition, different place to record. Get these mixed up and the code looks right and returns nonsense.

6. Traps

1. Recording in the wrong place. See above — it’s the single most common bug in this pattern.
2. Forgetting to undo state when shrinking. Whatever add() did, remove() must exactly reverse. Counts especially: decrement, and delete the key at zero if your validity test uses map size.
3. Using a window on an array with negative numbers and a sum constraint. Adding an element can shrink the sum, so the window isn’t monotone and shrinking doesn’t restore validity. That’s prefix sums + a hash map, not a window.
4. while vs if for the shrink. It has to be while — one removal may not be enough.

7. Problems, easiest first

1. Longest Substring Without Repeating Characters — the template with a set
2. Longest Repeating Character Replacement — validity becomes arithmetic
3. Minimum Window Substring — the minimise flavour, and the hard one