Give an interviewer s = "ADOBECODEBANC" and t = "ABC", and the answer they want back is "BANC": the shortest slice of s that contains an A, a B, and a C. Contiguous, not a subsequence. Miss the contiguous part and you’re solving a different, easier problem. Miss the “including duplicates” part and you fail the test case where t = "AABC".
Minimum Window Substring is LeetCode 76, and it sits in the Hard bucket for a reason. It turns up at Airbnb, Meta, and Amazon, usually as the second problem once you’ve cleared something lighter. The machinery underneath is the same sliding window you’d reach for on Longest Substring Without Repeating Characters, but the bookkeeping is fussier, and that fussiness is where most people lose the round.
What counts as covering t
The window covers t when it holds at least as many of every character as t asks for. If t = "AABC", a window with a single A does not cover it; you need two A’s, a B, and a C. The target is a multiset, so counts matter, not mere presence. This is the most common place a first draft breaks, because the instinct is to track “have I seen an A, a B, a C” with a set of booleans, which quietly loses the duplicate requirement.
Characters in s that never appear in t are noise. They still sit inside a candidate window and add to its length, so a valid answer can carry plenty of junk as long as the required characters are all present. “BANC” happens to be clean. “ADOBEC” is also a valid covering window, just longer, which is exactly why you keep shrinking.
The brute force, and why it’s too slow
The literal reading of the problem is to look at every substring of s, keep the ones that cover t, and return the shortest. A string of length n has roughly n²/2 substrings, and checking whether one covers t takes another pass, so the obvious version lands around O(n² · m). Even with rolling counts you’re at O(n²). For an s of length 10^5, that’s off the table before you’ve written the return statement.
The waste has a name once you look at it. Sliding the start forward one character throws away everything the previous window told you and recounts from scratch. A window that already covers t carries information: every window that starts no later and ends no earlier also covers t. That monotonic property is the thing you ride instead of recomputing.
Expand to cover, shrink to minimize
Keep two indices, left and right, both at the front. Walk right forward, pulling characters into the window, until the window covers t. The moment it does, stop growing and do the opposite: walk left forward, dropping characters, for as long as coverage holds. The step just before coverage breaks is the smallest window ending at the current right. Record its length if it beats your best, let left break coverage, then go back to growing right.
Both pointers only ever move forward. right crosses s once and left crosses at most the same distance, so the whole scan is O(n) no matter how the windows overlap. That’s the payoff: two pointers, each traversing the string a single time.
The counter that replaces comparing two maps
The delicate part is deciding, cheaply, whether the current window covers t. Comparing a window-frequency map against the target map on every step drags you back toward O(n · k), where k is the alphabet size. The move is to collapse “does the window cover t” into one integer.
Build a frequency map of t. Track a single number, call it missing, starting at len(t): the count of still-owed characters, duplicates included. When right pulls in a character the map still wants (its count is positive), decrement missing. Always decrement that character’s count, letting it slide negative for characters the window has in surplus. The window covers t exactly when missing reaches zero. Shrinking runs the same logic backward: when left drops a character whose count climbs back above zero, you removed a genuinely needed character, so missing ticks up again.
Negative counts are the quiet idea here. A count of −2 for some letter means the window holds two more than it needs, so removing one still leaves it covered and missing stays at zero. You never compare two maps. You watch one integer.
from collections import Counter
def min_window(s: str, t: str) -> str:
if not s or not t or len(t) > len(s):
return ""
need = Counter(t)
missing = len(t) # required characters not yet in the window
left = 0
best_len = float("inf")
best_start = 0
for right, ch in enumerate(s):
if need[ch] > 0: # this char was still owed
missing -= 1
need[ch] -= 1 # surplus characters go negative
while missing == 0: # window covers t, shrink from the left
if right - left + 1 < best_len:
best_len = right - left + 1
best_start = left
need[s[left]] += 1
if need[s[left]] > 0: # dropped a character the window needs
missing += 1
left += 1
return "" if best_len == float("inf") else s[best_start:best_start + best_len]
Run it on “ADOBECODEBANC” and “ABC”. The window first covers t at “ADOBEC”, can’t trim, grows again, and eventually settles on “BANC” when right reaches the final C and left has walked up to the B at index 9. Tracking best_start alongside best_len means you return the actual substring, which is what the problem asks for, rather than a length you’d have to reconstruct.
How the approaches compare
Below, n is the length of s, m the length of t, and k the number of distinct characters in t (at most 128 for ASCII, so the extra space is effectively constant for interview inputs).
| Approach | Time complexity | Extra space | Practical verdict |
|---|---|---|---|
| Every substring, recount coverage each time | O(n² · m) | O(k) | Dies on large inputs; only worth saying out loud as a baseline |
| Every substring with rolling counts | O(n²) | O(k) | Still too slow past roughly 10^4 characters |
| Sliding window with a coverage counter | O(n + m) | O(k) | The expected answer; one scan, k = distinct characters in t |
The mistake that breaks on repeated letters
Tracking coverage with a set of seen characters passes the sample case and dies on t = "AABC". A set records that you’ve seen an A; it cannot tell one A from two. The frequency map is what carries duplicate requirements, and because missing only decrements while a character’s required count is still positive, the second A you owe is tracked separately from the first. If an interviewer hands you a t with a repeated letter right after your first pass, this is the exact thing they’re probing.
The other quiet failure is the shrink condition. Shrinking while missing == 0 is right; shrinking one step too far, or recording the window after coverage has already broken, gives you a length that’s off by one or a window that doesn’t actually cover t. Record the best inside the loop, before the removal that breaks coverage, and the off-by-one disappears.
Follow-ups interviewers add
Once the O(n) solution is on the board, the conversation usually turns to variations. A few that come up, close to how they get asked:
- “What changes if
sandtcan hold any Unicode character rather than only uppercase letters?” The Counter already handles it; a fixed 128-slot array does not, so this really asks whether you hard-coded the alphabet. - “Return the length of the shortest window instead of the window itself.” Drop the
best_starttracking and returnbest_len, with a clean answer for the no-window case. - “What if
tis longer thans?” Thelen(t) > len(s)guard returns early. Say it before you write the loop, not after they catch it. - “Can you do it in constant extra space?” Not in general; you need counts proportional to the distinct characters in
t. Pushing back on an impossible constraint is part of the signal they want.
The idea is one sliding window. The Hard rating comes from how many ways there are to get the bookkeeping slightly wrong. People who’ve drilled the pattern write it in a few minutes; people who memorized a solution for Longest Substring and hoped it transfers spend the round debugging their coverage check. Get the missing counter clean once, understand why the counts go negative, and this stops being a Hard problem and turns into a warmup.
Drill the patterns next:
