Run it: Minimum window substring in code
The window with each valid state printed, its operation count against a brute force over every substring. And the >= variant of the counter update getting a copy case wrong.
The shape of the solution
Expand the window's right edge until it is valid. Contains all of it needed. Then contract the left edge as far as possible while it stays valid, recording the best window seen. Repeat.
The mechanism that makes this efficient is a counter of how many required characters are still missing. So validity is an O(1) check rather than a check of two dictionaries.
O(n + m) time. Space is O(k) for the alphabet.
Two lines carry the design.
if need[ch] > 0: missing -= 1 — the guard is important. Decrementing missing for every character would count surplus copies as progress. Only a copy that is still required reduces what is missing.
need[ch] -= 1 unconditionally, allowing negative values. A negative count means surplus, and it is exactly the condition the shrink loop tests: need[s[left]] < 0 means the character at the left edge is present more often than needed. So it can be dropped.
After recording a candidate, the left character is released and missing incremented — which invalidates the window on purpose. So the outer loop resumes expanding to find the next candidate.
The grow-then-shrink shape
Two phases alternating. Extend hi until the window satisfies the requirement; then advance lo as far as possible while it still does, recording the best window each time. When it stops being valid, go back to growing.
Every index is entered once by hi and left once by lo. So the total work is O(n) despite the nested loop. That is the same amortised argument as longest-substring-without-repeats and longest-in a row-sequence. A nested loop is not by itself quadratic.
The counter that makes it cheap
The naive validity test compares the window's counts against the requirement's. This is O(k) on every single step. Instead keep missing: the number of distinct required characters whose quota is not yet met.
Increment or decrement it only when a character's count crosses exactly its requirement — have[c] == need[c] on the way in, have[c] < need[c] on the way out. Using >= there is the classic bug, because surplus copies then decrement the counter repeatedly.
Copies, and the empty cases
If t is "AABC" the window needs two As. Counting rather than set membership handles that for free, and a set-based solution silently accepts one.
Handle t longer than s, either being empty, and no valid window existing. The last returns the empty string, which needs a sentinel that cannot be confused with a real window of length zero.
Tracing "ADOBECODEBANC" with "ABC"
| right | Character | Window when valid | Length | Best so far |
|---|
| 5 | C | ADOBEC | 6 | "ADOBEC" |
| 10 | A | CODEBA (left advanced past D, O, B, E) | 6 | "ADOBEC" |
| 12 | C | BANC | 4 | "BANC" |
The shrink step is the interesting part. At right = 5 the window "ADOBEC" is valid, and A at the left is not surplus, so nothing shrinks. The candidate is recorded, A is released, and expansion resumes.
Later, when the second A arrives at index 10, the window is valid again and the left edge advances past every surplus character — D, O, B, E — stopping at the C that is still needed. By right = 12 the window has narrowed to "BANC", length 4, which is the answer.
Recording (length, left, right) as a tuple lets a single check handle both "is this shorter" and "remember where it was". This is tidier than three separate variables.
The template this belongs to
The same expand-then-contract skeleton solves a large family. What varies is the validity condition and what is recorded.
| Problem | Valid when | Optimise |
|---|
| Minimum window substring | All required characters present | Minimise length |
| Longest substring without repeats | No character appears twice | Maximise length |
| Longest substring with at most k distinct | Distinct count ≤ k | Maximise length |
| Permutation in string | Window length = m and counts match | Existence |
| Find all anagrams | Same | Collect all positions |
| Minimum size subarray sum ≥ k | Sum ≥ k, values positive | Minimise length |
| Longest repeating character replacement | Length − most frequent ≤ k | Maximise length |
Minimise-length problems shrink while valid; maximise-length problems shrink while invalid. That single distinction decides the loop structure, and mixing them up is the most common way these solutions go wrong.
The precondition for the whole family is that validity be monotonic in the window. Extending a valid window keeps it valid, or extending an invalid one can only help. When that fails, as with negative numbers and a sum target, prefix sums replace the window.
Edge cases
| Case | Result |
|---|
t longer than s | "" — check upfront |
| Either string empty | "" |
t has repeats, s has fewer | "" |
s == t | s |
| Several windows of equal minimum length | Any one; confirm which is expected |
Characters in s not in t | Allowed inside the window |
| Case sensitivity | "a" and "A" are distinct unless told otherwise |
The "not enough copies" row is the one that catches set-based solutions: s = "a", t = "aa" must return "". And a set-based check reports success.