Minimum Window Substring
Return the shortest substring of s containing every character of t, including duplicates. Return the empty string if none exists.
Intuition
Two phases alternating: grow the right edge until the window contains everything t requires, then pull the left edge in as far as possible while it still does. Record the length each time the window is valid and minimal. The efficiency hinges on making the validity check O(1) — rather than re-scanning the frequency map after every move, keep a counter formed of how many distinct required characters have reached their required multiplicity. The window is valid exactly when formed equals the number of distinct characters in t.
The formed/required counter is what makes this linear. Rather than re-checking every character count on each step, track how many distinct characters have hit their exact quota, and compare that single number against the target. Grow to become valid, shrink while still valid, record at every valid moment.
Approach
Build the requirement map
Count the characters of t, including duplicates: t = "AABC" requires two As. Let required be the number of distinct characters. This distinction matters — the window must satisfy every character's full count, but formed tracks how many characters have been fully satisfied, not how many total characters have been seen.
Grow until valid, tracking formed in O(1)
Advance the right edge, incrementing the window's count for each character. When a character's window count exactly equals its required count, increment formed. Using equality rather than >= is essential: a fourth A when only two are needed must not increment formed again. When formed == required the window contains everything.
Shrink while valid, then break validity and resume
Once valid, pull the left edge inward. Each removal decrements a count; when a required character's count drops below its requirement, decrement formed and stop shrinking. Before each removal, if the current window is shorter than the best recorded, update the answer. Then resume growing the right edge. Every index is touched at most twice — once by each pointer — so the whole algorithm is O(|s| + |t|).
Solution & live demo
Common pitfalls
Using >= when updating formed
if ch in need and have[ch] >= need[ch]:
formed += 1if ch in need and have[ch] == need[ch]:
formed += 1With >=, every extra copy of an already-satisfied character increments formed again, so it races past required and the validity test becomes meaningless. The counter must fire exactly once, on the transition to satisfied.
Recording the answer outside the shrink loop
while formed == required:
...
left += 1
if ...: best = ...while formed == required:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right)
...The minimum window for a given right endpoint appears during the shrink, just before validity breaks. Recording after the loop captures an already-invalid window and misses the real minimum.
Treating any missing character as breaking validity
have[lc] -= 1 formed -= 1
have[lc] -= 1
if lc in need and have[lc] < need[lc]:
formed -= 1Removing a surplus copy of a character, or one not in t at all, leaves the window valid. Decrementing unconditionally ends the shrink prematurely and reports a window larger than necessary.
Edge cases
The window can never satisfy every requirement, formed never reaches required, and the empty string is returned.
The requirement map stores counts, and formed only increments on exact equality, so a window with one A does not satisfy a requirement of two.
The whole string is the answer; the window becomes valid at the last character and cannot shrink.
They are tracked in the window counts but never affect formed, so they are freely discarded during the shrink phase.