Minimum Window Substring, without the hand-waving

Minimum Window Substring is LeetCode #76, and it has a reputation problem: everyone can recite “expand right, shrink left,” and almost nobody can say when it’s safe to shrink. That gap is exactly where interviews go sideways.

The fix is to stop thinking in movements and start thinking in an invariant: the window always covers t, or we’re expanding until it does. Every line of the solution is either restoring or exploiting that invariant.

while right < len(s):
    window[s[right]] += 1
    if window[s[right]] == need[s[right]]:
        have += 1
    while have == len(need):  # invariant holds — harvest & shrink
        best = min(best, window_size)
        shrink(left)
    right += 1

Notice what the have / need counters buy you: instead of comparing two hash maps on every step — O(k) each time — you maintain a single integer that tells you whether the invariant holds. That’s the difference between “roughly O(n)” and a Big-O you can defend under follow-up questions.

Coach’s note · When this problem comes back on your queue, try stating the invariant out loud before writing a single line. If you can’t, the review counts — that’s the point.

Deriving the shrink condition

Why is have == len(need) the right guard? Because it’s the cheapest possible statement of “the window currently covers t.” need maps each required character to its required count. have counts how many of those characters have fully met their quota inside the window.

Two details people fumble:

• have only increments when a character’s window count becomes exactly equal to its needed count. Going past the quota changes nothing — the character was already satisfied.
• Symmetrically, when shrinking drops a character’s count below its quota, have decrements. Any other bookkeeping double-counts.

Once you see it this way, the shrink loop stops being scary. While the invariant holds, the current window is a candidate answer — so record it, then shrink from the left until the invariant breaks. The moment it breaks, you’re back in expansion mode. There is no third state.

Walking ADOBECODEBANC

Take s = "ADOBECODEBANC", t = "ABC". The right pointer expands until the window first covers t at "ADOBEC" — that’s a candidate of length 6. Now shrink: dropping A breaks coverage, so expansion resumes. The next time have == need, the window is "DOBECODEBA" → shrink to "CODEBA" (length 6 again). The final expansion reaches "BANC" — shrink stops at length 4, and nothing shorter ever satisfies the invariant. Answer: "BANC".

Every character enters the window once and leaves at most once. Two pointers, each moving monotonically rightward — that’s the amortized argument for O(n), and it’s worth saying exactly that sentence in an interview.

The follow-ups interviewers actually ask

“What if s is a stream?” The two-pointer window breaks — you can’t rewind a stream to shrink. The honest answer: you’d need to buffer the last W characters (bounded memory only if the answer length is bounded), or accept an approximation. Recognizing that the algorithm’s random-access assumption is load-bearing is the senior-signal answer.

“What if t has duplicates?” Nothing changes — and saying why is the point. need already stores counts, not membership. t = "AABC" just means need["A"] == 2, and have only credits A once its window count reaches 2. If your mental model was a set instead of a counter, this follow-up is where it collapses.

The pattern to retain: sliding window problems are invariant problems. Name the invariant first; the pointer movements fall out of it.