Sliding Window
Have and need
The hardest window in the set: grow until the window is sufficient, then shrink while keeping it sufficient.
Key idea
The rule runs the other way
Every window so far has been legal when it is small enough and illegal when it grows too far. Shrinking restored legality.
Minimum-window problems invert this. The window is only useful once it is large enough to contain everything required. Shrinking now threatens usefulness rather than restoring it, so the loop changes shape: grow until sufficient, then shrink while still sufficient, recording as you go.
Here is that shape on a simpler requirement than the problem below: the shortest stretch containing at least k distinct characters.
Why it works
Record inside the shrink loop
In the maximizing windows, the recording line sat after the shrink loop, because that is where the window was legal. Here it sits inside the shrink loop, because that is where the window is sufficient.
Same principle both times: record exactly where the invariant you care about holds. Getting this placement wrong is the single most common bug in minimum-window code, and it produces answers that are close but consistently too large.
Key idea
Sufficiency with multiplicities
Counting distinct characters is easy because each character contributes once. The real problem needs multiplicities: a target may demand two copies of a character, and a window holding one is not sufficient.
Comparing full count maps on every step works and costs the alphabet size per step. The standard alternative is to carry two numbers.
Why it works
The two numbers
need is how many distinct characters must reach their required count. It is fixed once the target is read.
have is how many of those characters currently sit at or above their required count in the window. The window is sufficient exactly when have == need.
Update have only on the exact transition. When a character's window count rises to precisely its requirement, have goes up by one. When it falls to precisely one below, have goes down by one. Using a comparison such as greater-than-or-equal instead of exact equality double counts and quietly breaks everything.
Gotcha
Increment on equality, not on sufficiency
If you increment have whenever a character's count is at least its requirement, then a window holding four copies of a character that only needs two increments have three extra times, and the window is declared sufficient long before it is.
The rule is a transition, not a state. have changes only at the moment a character crosses the line, in either direction.
Tip
Return the window, not its length
When the answer is the substring itself rather than its length, record the start index alongside the best length and slice at the end. Slicing on every improvement works too and wastes time copying strings you are about to discard.
Track best_start and best_length, then return the single slice once. Also decide up front what an impossible case returns, usually the empty string, and make sure the initial best_length is large enough that it never wins.
Before you start
Write down four things: what the window remembers, what makes it sufficient, where you record, and what you return when nothing works. If all four are on paper before you type, this problem is mechanical. If they are not, it is very hard.
Predict the output: incrementing on the wrong condition
This counts how many characters have met their requirement, but uses the wrong condition. Type what it prints.
Build the sufficiency tracker
Build the piece that the problem needs, on its own. make_requirement turns a string into a count map. update_have takes the window counts, the requirement, a character, and the direction it moved (+1 entering or -1 leaving), applies the change, and returns the delta that should be applied to have, which is 1, -1, or 0. is_sufficient reports whether every requirement is met.
Tests
req = make_requirement("aabc")
print(req)
window = {}
print(update_have(window, req, "a", 1), update_have(window, req, "a", 1))
print(update_have(window, req, "b", 1), update_have(window, req, "a", 1))
print(update_have(window, req, "a", -1))
print(update_have(window, req, "a", -1))
print(is_sufficient({"a": 2, "b": 1, "c": 1}, req), is_sufficient({"a": 1, "b": 1, "c": 1}, req))Output
Run the tests when you are ready.
Minimum Window Substring
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.