STEP 10 · SLIDING WINDOW · EXPAND, THEN TIGHTEN · HARD

Minimum Window Substring

WHAT IT SAYS

Given strings s and t, find the shortest substring of s that contains every character of t, including repeats.

WHAT IT'S REALLY ASKING

"Coverage is a one-way door: once a window contains everything you need, stretching it further can never take that away. So for each right end there is exactly one window worth considering — the tightest one that still covers — and every other window ending there is just a longer version of it, carrying dead weight on the left. Find the tightest left edge for each right end, and you've found the answer among n candidates instead of n²."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Every substring, check if it covers

O(n² · |t|) time, O(|t|) space

Take every pair of endpoints, tally the characters between them, and check the tally against t's requirements — including multiplicities, since t may ask for two A's. Keep the shortest one that passes. Nothing is missed, so it's correct.

WHERE THE WORK IS WASTED — You re-answer a question that can't change its mind. Once s[l..r] covers t, every longer end r+1, r+2, … also covers it — adding characters cannot remove one — yet the inner loop dutifully re-tallies and re-checks each of them, and every one of those windows is *worse* than the one you already found, because it's longer with the same left edge. The tally is rebuilt from scratch too, when consecutive windows differ by exactly one character.

KEY OBSERVATION — THE UNLOCKlink

Coverage survives growth. So only the tightest window can win.

Two facts, and the algorithm has nowhere left to hide. First: for a fixed right end r, if start l covers t then every start to the left of l covers it too — a bigger window can only contain more. So the valid starts form a solid block from 0 up to some tightest cutoff m(r), and among all windows ending at r, the only one that could ever be the answer is [m(r)..r]. Every other valid window ending at r has the same right edge and a left edge further back — strictly longer, strictly worse. That kills the n² search on its own: there are only n candidates, one per right end. Second, and this is what makes finding m(r) cheap: m never moves backwards. If [m(r)..r] covers t, then [m(r)..r+1] covers it too, so the tightest start for r+1 is at m(r) or beyond — it cannot be earlier. The left edge therefore only ever advances, across the entire scan, which is why a shrink loop nested inside an expand loop still costs O(n) total: each index is evicted at most once in its life. What you shrink away is surplus. A character can be inside the window and still be useless — the third A when t only asks for two — and those are precisely the ones the left edge can discard for free. The moment removing a character would drop a requirement below its quota, you've hit m(r), and you stop.

Expand until covered, then tighten until it hurts

O(n + |t|) time, O(|t|) space

Walk the right edge forward, tallying characters and tracking how many of t's requirements are fully met. The instant every requirement is met, pull the left edge in as long as the window still covers — discarding leading characters that t doesn't need and surplus copies of ones it does — and record the width when you can't tighten any further. Then push the right edge on and repeat; the answer is the smallest width you ever recorded.

Make 'does it cover?' an O(1) question

O(n) time with an O(1) validity check, O(|t|) space

Comparing two frequency maps on every step is the naive way to test coverage. Instead keep a single integer: how many of t's *distinct* characters have currently met their full required count. Bump it only when a character's count rises to exactly its requirement (surplus copies past that point change nothing), and drop it only when a count falls from exactly the requirement to one below — so the window covers precisely when that integer equals the number of distinct characters in t.

WHAT YOU TRADED — You pay O(|t|) memory and inherit the usual precondition — the window only works because coverage is monotone in width. The lesson is the orientation: for an 'at least' requirement, growing helps, so you expand to become valid and then shrink to become optimal; for an 'at most' budget, growing hurts, so you shrink to become valid at all. Same two pointers, opposite reasons for moving them — and reaching for the wrong one is how people end up shrinking a window that was never valid to begin with.

WATCH THE IDEA RUN

width 0

shortest cover —

requirements met 0 / 3

Looking for the shortest window covering 'ABC'. Expand until it covers, then squeeze from the left — the squeeze is where the answer actually gets found.

step 1 / 16

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Expand to Cover, Shrink to Tighten

YOU'LL SEE IT AGAIN WHEN

You want the shortest contiguous stretch satisfying a requirement that growing can only help — a coverage, a threshold, a 'contains all of X'.
For a fixed right end, valid starts run back in an unbroken block, so exactly one window per right end is worth evaluating: the tightest.
The requirement counts multiplicities, so an element can be inside the window and still be surplus — free to discard.
You need to know 'am I still valid?' as elements leave, which means maintaining a satisfaction counter rather than re-checking the whole state.

SAME BLUEPRINT, DIFFERENT PROBLEM

Minimum Size Subarray SumNumber of Substrings Containing All Three CharactersPermutation in StringSmallest Range Covering Elements from K Lists

The bar isn't "solved it once." It's "could rebuild it from the observation."