Use the Minimum Window Substring interview invariant to prove validity, handle duplicates, and shrink pointers on ADOBECODEBANC fast.
Most candidates who blank on this problem in interviews don't blank because they forgot the algorithm. They blank because they never separated the two things the problem is actually asking: how do you know a window is valid, and how do you know it's the smallest valid one? Those are different questions, and conflating them is why minimum window substring interview explanations so often trail off into hand-waving right when the interviewer leans in.
The good news is that once you can state the window-validity invariant in plain English, the whole solution stops feeling like a memorized trick and starts feeling like an inevitable consequence of the rule you already know. That's the shift this guide is built around.
What Minimum Window Substring Is Actually Asking You to Prove
The problem is not 'find a substring' — it's 'prove this one is the smallest valid one'
The standard framing is: given string `s` and string `t`, find the minimum-length substring of `s` that contains all characters of `t`. Simple enough to read. The structural mistake most candidates make is treating that as a search problem when it's actually a proof problem. Finding a valid window is easy — any window that covers all of `t` qualifies. The hard part is proving that the window you return is the smallest one, and that requires a formal definition of what valid even means before you write a single line of code.
Candidates who jump straight to the two-pointer loop without defining validity first produce explanations that wobble. They can describe what the code does, but they can't explain why shrinking the left pointer is safe, or why the minimum they find is actually the minimum. That's the gap interviewers hear.
What this looks like in practice
Take the canonical example: `s = "ADOBECODEBANC"`, `t = "ABC"`. There are multiple valid windows in that string — `"ADOBEC"` is valid, `"DOBECODEBA"` is valid, `"BANC"` is valid. The problem isn't identifying any of them. The problem is arriving at `"BANC"` and being able to say, with confidence, that nothing smaller exists. That claim requires a structural argument, not just a scan. The algorithm earns the minimum by expanding until valid, then shrinking as far as validity allows, and recording the best it finds at each valid state. Every step of that loop is a consequence of the invariant — which is exactly what the interviewer is waiting for you to articulate.
State the Window-Validity Invariant Before You Touch Code
The one invariant that keeps the whole thing honest
Here is the invariant, stated plainly: a window is valid if and only if, for every character `c` in `t`, the number of times `c` appears in the current window is greater than or equal to the number of times `c` is required by `t`. Not just that the character is present. Not just that the right characters are somewhere in the window. The counts must meet or exceed the requirements, for every character, simultaneously.
This is the sentence worth writing on the whiteboard before anything else. It makes validity a binary, checkable state rather than a vague feeling. And it's the foundation every other piece of the algorithm rests on.
What this looks like in practice
The standard implementation tracks this with two frequency maps: `need`, which stores the required count of each character from `t`, and `window`, which stores the observed count of each character in the current window. A third variable — call it `matched` — counts how many distinct characters from `t` have been fully satisfied (i.e., `window[c] >= need[c]`). The window is valid exactly when `matched == len(need)`.
This matters because validity is a state you enter and exit as the pointers move. When you add a character to the right and it tips `window[c]` from `need[c] - 1` to `need[c]`, you increment `matched`. When you remove a character from the left and it drops `window[c]` below `need[c]`, you decrement `matched`. The invariant is always either satisfied or not — there's no ambiguity, which is exactly what makes the algorithm trustworthy.
Why the interviewer cares more about this than your code shape
A candidate who can recite the two-pointer loop but can't explain why it's correct is, from an interviewer's perspective, a candidate who memorized a solution. A candidate who states the invariant first and then derives the loop from it is a candidate who understands the problem. The syntax of the implementation is recoverable under pressure. The reasoning is not — unless you actually own it.
The invariant is the correctness story. When an interviewer asks "why is it safe to shrink the left pointer here?", the answer is: because the window is still valid, so you haven't lost anything required. That answer only comes naturally if you started with the invariant, not with the code. According to Introduction to Algorithms (CLRS), invariant-based reasoning is precisely what distinguishes a correct algorithm from one that happens to produce correct output on the test cases you tried.
Handle Duplicate Characters in t Without Breaking the Count
Why 'has the character' is the wrong test
The most common bug in minimum substring problem solutions isn't a syntax error. It's a conceptual one: treating character membership as coverage. If `t = "AABC"`, a window that contains one `A`, one `B`, and one `C` is not valid. It needs two `A`s. A candidate who checks `'A' in window` instead of `window['A'] >= need['A']` will produce a solution that passes simple test cases and fails the moment duplicates appear.
This is exactly where interviewers probe. They'll ask you to trace through a case with duplicate characters in `t`, and if your mental model is "does the window contain all the characters in `t`?", you'll give the wrong answer.
What this looks like in practice
Say `t = "AABC"`. The `need` map is `{'A': 2, 'B': 1, 'C': 1}`. A window containing `"ABC"` has `window = {'A': 1, 'B': 1, 'C': 1}`. The `A` count is 1, but the requirement is 2. The invariant is not satisfied — `matched` should only increment for `A` when `window['A']` reaches 2, not when it reaches 1. Until that second `A` enters the window, the window is invalid no matter how many other characters it covers.
The `matched` counter handles this cleanly: you only increment it when `window[c]` crosses from `need[c] - 1` to exactly `need[c]`. One occurrence of `A` does not trigger the increment. The second one does. This is why the count-based approach is not an optimization — it's a correctness requirement.
The easy way to say it out loud in an interview
The verbal distinction is simple: required frequency versus observed frequency. If the observed frequency of every character meets or exceeds the required frequency, the window is valid. If any character's observed frequency falls short of its required frequency, the window is invalid. Saying it this way makes the duplicate logic obvious rather than a special case. The GeeksforGeeks sliding window explanation covers the frequency-map setup, though the invariant framing is rarely made this explicit.
Expand Right, Then Shrink Left Only While the Window Stays Valid
Why the shrink step is safe and when it stops being safe
This is the correctness move most candidates skip. Shrinking the left pointer is safe for exactly one reason: the window is still valid after the shrink. The moment the window becomes invalid — meaning `matched` drops below `len(need)` — you must stop shrinking. Continuing to shrink past that point would discard a required character, and the window would no longer contain all of `t`. The minimum you recorded at the last valid state is the real minimum for that right-pointer position.
This is not a heuristic. It's a direct consequence of the invariant. If the invariant is satisfied, shrinking is safe. If it's not, shrinking is not. The algorithm is correct because it respects that boundary every time.
What this looks like in practice
The control flow, stated plainly: expand the right pointer until the window is valid (`matched == len(need)`). Once valid, record the current window size as a candidate minimum. Then shrink the left pointer — updating `window` and `matched` as you go — and keep shrinking as long as the window remains valid, recording a new candidate minimum each time. When the window becomes invalid, stop shrinking and resume expanding the right pointer. Repeat until the right pointer has traversed all of `s`.
This sliding window interview problem pattern is two nested phases: expand-to-valid, then shrink-to-minimum. Neither phase is optional. The expand phase finds validity. The shrink phase finds minimality. Both are required to solve the problem correctly.
The part people hand-wave and get burned by
The failure mode is stopping after the first valid window instead of continuing to shrink. A candidate who records the first valid window and moves on will get the right answer on simple examples but fail on strings where the minimum window comes after multiple rounds of expansion and contraction. The `while matched == len(need)` loop is not a detail — it's the mechanism that finds the minimum rather than just a valid window. Skipping it produces a correct-looking but fundamentally broken solution.
Dry Run ADOBECODEBANC Until the Pattern Stops Looking Random
Why ADOBECODEBANC is the right example to memorize
This string is the standard example for a reason: it forces both phases of the algorithm to play out visibly. It's long enough that the expansion phase produces multiple valid windows, and the shrink phase actually changes the answer. If you can trace through it and explain each state transition, you can explain the algorithm. According to the LeetCode problem statement for Minimum Window Substring (Problem 76), the expected output for `s = "ADOBECODEBANC"`, `t = "ABC"` is `"BANC"` — and getting there requires understanding why earlier valid windows are not the minimum.
What this looks like in practice
Here is the key trace, using two pointers with frequency map state:
- Right expands: `A` → `D` → `O` → `B` → `E` → `C`. At `C`, window is `"ADOBEC"`, all of `ABC` covered. `matched = 3`. First valid window, length 6.
- Shrink left: remove `A`. `window['A']` drops to 0, below `need['A'] = 1`. `matched` drops to 2. Window invalid. Stop shrinking.
- Right expands: `O` → `D` → `E` → `B`. Window is `"DOBECODEB"`. Still missing `A`. Keep expanding.
- Right reaches `A`. Window is `"DOBECODEBA"`. `matched = 3` again. Valid. Length 10 — worse than 6.
- Shrink left: remove `D`, `O`, `B`, `E`, `C`, `O`, `D`, `E`. Each removal is safe because `A`, `B`, `C` are still covered. Window shrinks to `"BA"` — but `C` is gone. Invalid.
- Right expands: `N` → `C`. Window is `"BANC"`. `matched = 3`. Valid. Length 4 — new minimum.
- Shrink left: remove `B`. `window['B']` drops below `need['B']`. Invalid. Stop.
- Right pointer exhausted. Return `"BANC"`.
The moment the window gets smaller and smarter
The critical transition is when the algorithm arrives at `"BANC"` after the second expansion phase. At that point, the window is valid, length 4, which beats the previous best of 6. The algorithm records it. Then it tries to shrink further, immediately loses `B`, and stops. That sequence — valid, record, shrink-until-invalid — is the invariant in action. The answer `"BANC"` is not a guess. It's the consequence of a rule applied consistently.
Say the Answer Like You Mean It in a 60-Second Interview Explanation
The version that sounds confident instead of memorized
Here is what a minimum window substring interview explanation sounds like when the candidate owns the invariant:
"The goal is to find the shortest substring of `s` that contains every character in `t` with at least the required frequency. I'll use two pointers and a frequency map. The key invariant is: a window is valid when the observed count of every character in `t` meets or exceeds its required count. I track this with a `matched` counter — it increments when a character's count hits exactly the required threshold, and decrements when it falls below.
The loop has two phases: expand the right pointer until the window is valid, then shrink the left pointer as long as validity holds, recording the window size each time. The minimum across all valid states is the answer. Time complexity is O(n + m) — each pointer moves forward at most n times, and the frequency maps are bounded by the character set size. Space is O(m) for the maps, or O(1) if you use a fixed 128-element array for ASCII."
What this looks like in practice
Notice what that explanation does: it starts with the goal, states the invariant explicitly, describes the state variable, explains the two-phase loop, and closes with complexity. It does not start with "so I use a sliding window" and hope the interviewer fills in the gaps. The invariant is the second sentence, not an afterthought. That ordering signals that the candidate understands correctness, not just implementation.
Know the Bugs That Make Good Solutions Fail in Interviews
The classic mistakes: off-by-one, stale counts, and pretending duplicates do not matter
Three bugs account for the majority of minimum substring problem failures in practice.
Membership instead of count. Using `c in window` instead of `window[c] >= need[c]` to check validity. Fails immediately on any `t` with duplicate characters.
Not decrementing `matched` on shrink. Removing a character from the left, updating `window[c]`, but forgetting to check whether `window[c]` has dropped below `need[c]` and decrement `matched` accordingly. The window appears valid longer than it is, and the minimum gets recorded incorrectly.
Recording the best window outside the valid state. Updating the minimum answer when `matched < len(need)` — usually because the candidate checks for a new minimum at the wrong point in the loop, before confirming validity.
What this looks like in practice
The membership bug produces a window like `"ABC"` when `t = "AABC"` and calls it valid. The stale-count bug produces a shrink loop that continues past the point of validity, discarding a required character and recording a minimum that doesn't actually contain all of `t`. The wrong-placement bug records a window that's too large or too small because the update happens at the wrong moment in the control flow.
Each of these is a structural error, not a typo. They come from a fuzzy model of what validity means, not from careless coding.
The reassurance most candidates need
If you've made any of these mistakes, you didn't make them because you're bad at algorithms. You made them because you started with the code shape instead of the invariant. Once the invariant is clear — valid means all required frequencies are met — every one of these bugs becomes obviously wrong before you even run the code.
Explain the Complexity Without Sounding Like You Memorized a Cheat Sheet
Why this is linear even though the pointers move a lot
The time complexity is O(n + m), where n is the length of `s` and m is the length of `t`. The argument is simple: the left pointer and the right pointer each move forward at most n times, and they never move backward. The total number of pointer operations is bounded by 2n. The initial setup of the `need` map is O(m). Combined, that's O(n + m). The algorithm is linear not because of a clever trick but because of a structural property: two pointers with frequency map state, where each pointer is monotonically non-decreasing.
What this looks like in practice
Space complexity is O(|Σ|), where Σ is the character set. For a frequency map implemented as a hash map, the space is bounded by the number of distinct characters in `s` and `t`. In practice, that's at most 52 for case-sensitive alphabetic input, or 128 for full ASCII.
When a fixed-size array beats a hash map
If the input is guaranteed to be ASCII, a fixed-size array of length 128 is faster than a hash map in practice: no hashing, no collision handling, direct index access. If the input can be Unicode — arbitrary code points — a hash map is required because the character space is too large for a fixed array. Knowing this distinction and being able to state it cleanly signals that the candidate has thought about real implementation tradeoffs, not just theoretical complexity.
Use the Same Pattern on the Right Problems, and Skip It on the Wrong Ones
When this pattern fits and when it does not
The sliding window interview problem pattern applies when: the validity condition depends on the frequency of characters in a contiguous window, the window can be expanded and contracted by moving two pointers forward, and the optimal answer is found by minimizing or maximizing window size subject to the validity condition. Minimum Window Substring fits all three.
It does not apply when: the order of characters inside the window matters (subsequence problems), the validity condition requires non-contiguous matching, or the constraint is on something other than character frequency. Confusing substring problems with subsequence problems is a common pattern-matching error.
What this looks like in practice
Anagram detection in a string (find all start indices where a permutation of `t` appears in `s`) uses the same frequency-map and two-pointer structure, but the validity condition is stricter: exact counts, not at-least counts, and a fixed window size. Minimum Window Subsequence is superficially similar but fundamentally different: it requires characters to appear in order, which breaks the shrink-left logic entirely and demands a different approach.
The boundary is clear once you ask the right question: does validity depend on frequency in a contiguous window, or does order inside the window matter? If order matters, this pattern doesn't apply.
The transferable lesson interviewers actually care about
The real skill being tested is not whether you memorized the minimum window substring algorithm. It's whether you can identify the invariant that governs a problem, build a state machine around it, and reason about correctness from that foundation. That skill transfers to every sliding-window problem, and to a much wider class of problems where the key insight is defining what "valid" means before writing any code. According to Skiena's Algorithm Design Manual, the ability to articulate problem invariants is a consistent differentiator between candidates who solve problems and candidates who explain solutions.
How Verve AI Can Help You Prepare for Your Interview With Minimum Window Substring
The hardest part of this problem isn't writing the code. It's explaining the invariant out loud, under live pressure, to someone who is actively probing for gaps. That's a performance skill, and performance skills require live reps — not more reading.
Verve AI Interview Copilot is built for exactly this gap. It listens in real-time to your spoken explanation and responds to what you actually said, not a canned prompt. When you say "I use a sliding window" and stop there, Verve AI Interview Copilot can follow up the way a real interviewer would: "Why is it safe to shrink the left pointer?" — and you have to answer, live, with the invariant you either own or don't. That's the rep that matters. Verve AI Interview Copilot also stays invisible during screen-share sessions at the OS level, so if you're doing a mock with a peer or a coach, the tool is there without being a distraction. The 60-second explanation in Section 6 is worth rehearsing out loud at least five times before your interview. Verve AI Interview Copilot is the fastest way to get honest, immediate feedback on whether it sounds like understanding or recitation.
FAQ
Q: What is the minimum-window invariant, and how do you know when a window is valid?
A window is valid when the observed count of every character in `t` meets or exceeds its required count — not just that the character is present, but that it appears at least as many times as `t` requires. You track this with a `matched` counter that equals `len(need)` when the invariant is fully satisfied. If `matched < len(need)`, the window is invalid regardless of its size.
Q: How do duplicates in t change the counting logic?
Duplicates mean you cannot use membership tests — you must compare observed frequency against required frequency for every character. If `t = "AABC"`, a window needs two `A`s to satisfy the `A` requirement. The `matched` counter increments for `A` only when `window['A']` reaches `need['A'] = 2`, not when it reaches 1. One `A` in the window does not make the window valid.
Q: How do you shrink the left pointer without breaking correctness?
You shrink only while the window remains valid — that is, while `matched == len(need)`. Each time you remove a character from the left, you update `window[c]` and check whether `window[c]` has dropped below `need[c]`. If it has, you decrement `matched` and stop shrinking. The invariant guarantees that every window you record during the shrink phase is genuinely valid, so the minimum among them is a true minimum.
Q: What would a clean interview explanation sound like in 60 seconds?
Start with the goal: find the shortest substring of `s` containing all characters of `t` at required frequencies. State the invariant: a window is valid when every character's observed count meets its required count. Describe the mechanism: a `matched` counter that tracks how many characters are fully satisfied. Explain the loop: expand right until valid, shrink left while valid, record the minimum at each valid state. Close with complexity: O(n + m) time, O(|Σ|) space. That's the full explanation, in order.
Q: What are the most common bugs candidates make on this problem?
Three bugs dominate: using membership (`c in window`) instead of count comparison (`window[c] >= need[c]`), failing to decrement `matched` when a character's count drops below the requirement during the shrink phase, and recording the best window at the wrong point in the loop — before confirming that the window is valid. All three stem from a fuzzy definition of validity, not from coding errors.
Q: How does this pattern transfer to other sliding-window interview questions?
The pattern applies whenever validity depends on character frequency in a contiguous window and the optimal answer minimizes or maximizes window size. Anagram detection uses the same structure with exact counts and a fixed window size. Minimum Window Subsequence looks similar but requires ordered matching, which breaks the shrink-left logic. The transferable skill is asking: does validity depend on frequency in a contiguous window, or does order inside the window matter?
Q: How do you dry-run ADOBECODEBANC step by step?
Expand right through `"ADOBEC"` — first valid window, length 6. Shrink left: remove `A`, window becomes invalid, stop. Expand right through `"DOBECODEBA"` — valid again, length 10, worse. Shrink left as far as validity holds. Expand right through `"BANC"` — valid, length 4, new minimum. Try to shrink: remove `B`, invalid, stop. Right pointer exhausted. Return `"BANC"`. The key is tracing `matched` at each step to confirm when validity is entered and exited.
Conclusion
This problem is not a trick. It never was. The reason it feels like one is that most explanations skip straight to the implementation and leave the invariant implicit — which means the moment an interviewer asks "why does this work?", there's nothing to say.
The invariant is the answer: a window is valid when every required character appears at least as many times as `t` requires. Everything else — the frequency maps, the `matched` counter, the expand-then-shrink loop — is a direct consequence of tracking that condition precisely. Once you own the invariant, the code follows. Once you can say the invariant out loud, the explanation follows.
Before your next interview, do two things: rehearse the 60-second explanation from Section 6 until it sounds like a thought, not a recitation, and trace through ADOBECODEBANC by hand until you can call out the state of `matched` at every step without looking. Those two reps will do more for your performance under pressure than any amount of re-reading.
Riley Patel
Interview Guidance
