vizlearn

Minimum window substring

Interview QuestionsBy Updated

Grow the window on the right until it contains everything, then shrink it from the left while it still does. The trick that keeps it O(n) is tracking a single count of unsatisfied characters rather than comparing two dictionaries on every step.

Overview

The problem

Find the shortest substring of s containing all characters of t, including duplicates.

stAnswer
"ADOBECODEBANC""ABC""BANC"
"a""a""a"
"a""aa""" — not enough copies
"ab""b""b"

Three details to pin down before writing anything:

Duplicates count. If t = "AABC", the window needs two As. This is why a set is insufficient and a frequency count is required. Order does not matter. The characters may appear in any arrangement. The substring is contiguous, and characters not in t are allowed inside the window.

The brute force checks every substring: O(n²) substrings, each validated in O(m), so O(n²m). The answer is a sliding window in O(n + m).

StringsCoding problemHard

Step through it

What to watch

  • The window grows on the right and shrinks on the left — never the reverse.
  • Shrinking continues while the window is still valid, not just once.
  • Both pointers move forward only, which is what makes it linear.

Say this out loud

"Sliding window: expand right until the window is valid, then contract left while it stays valid, recording the best. I keep a counter of how many required characters are still short, so checking validity is one integer comparison rather than a dict comparison. O(n)."

Minimum window substring

Find the smallest substring of s that contains every character of t, including duplicates.

Run it

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 duplicate case wrong.

1Python
Output
2Python
Output
3Python
Output

                

                

                    
The shape of the solution

                    
Expand the window's right edge until it is valid — contains everything 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 comparison of two dictionaries.
4Python
Output
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 essential. 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 deliberately, 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-consecutive-sequence — a nested loop is not automatically quadratic.

                

                

                    
The counter that makes it cheap

                    
The naive validity test compares the window's counts against the requirement's, which 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.

                

                

                    
Duplicates, 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"

                    
rightCharacterWindow when validLengthBest so far
5CADOBEC6"ADOBEC"
10ACODEBA (left advanced past D, O, B, E)6"ADOBEC"
12CBANC4"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 comparison handle both "is this shorter" and "remember where it was", which 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.
ProblemValid whenOptimise
Minimum window substringAll required characters presentMinimise length
Longest substring without repeatsNo character appears twiceMaximise length
Longest substring with at most k distinctDistinct count ≤ kMaximise length
Permutation in stringWindow length = m and counts matchExistence
Find all anagramsSameCollect all positions
Minimum size subarray sum ≥ kSum ≥ k, values positiveMinimise length
Longest repeating character replacementLength − most frequent ≤ kMaximise length
Minimise-length problems shrink while valid; maximise-length problems shrink while invalid. That single distinction determines 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

                    
CaseResult
t longer than s"" — check upfront
Either string empty""
t has repeats, s has fewer""
s == ts
Several windows of equal minimum lengthAny one; confirm which is expected
Characters in s not in tAllowed 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.

                

                

                    
What it is testing

                    
Do you handle duplicate requirements? A Counter, not a set.
Do you find the O(1) validity check? A single missing counter, rather than comparing dictionaries on every step.
Do you guard the missing decrement? Only characters still needed count as progress.
Do you allow negative counts? They encode surplus, which is what the shrink loop keys on.
Do you shrink at the right time? Minimise-length shrinks while the window stays valid.
Can you place it in the template? Recognising the family, and naming the shrink-while-valid versus shrink-while-invalid distinction, is what makes the pattern reusable.

                

                

                    
Recap in one screen

                    
  • Expand the right edge until the window is valid, then contract the left edge while it stays valid, recording the shortest.
  • Use a Counter for requirements and a single missing total so validity is O(1).
  • Decrement missing only for characters that are still needed; let counts go negative to mark surplus.
  • After recording a candidate, release the left character to resume expanding.
  • O(n + m) time; minimise-length problems shrink while valid, maximise-length problems shrink while invalid.

                

            


        

    



How the code works
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 duplicate case wrong.
How the code works
  1. if have[ch] == need[ch]: missing -= 1Only when the count crosses the requirement exactly. Using >= fires again on every surplus copy, so the window is declared valid too early — the last block shows it.
  2. while missing == 0:A while, not an if. After recording a valid window you keep shrinking as long as it stays valid, which is where the minimum comes from.
  3. best = (0, -1)A sentinel that cannot be confused with a real window. Using the empty string instead makes "no window found" and "window of length zero" indistinguishable.
  4. Counter rather than a sett = "AABC" needs two As. A set-based check accepts one and is wrong on exactly the input the question will use.
Change one thing
  • Set t = s. The only valid window is the whole string, and the shrink loop never fires.
  • Print missing each iteration. Watching it fall to zero and bounce back is the clearest picture of the two phases.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why is the shrink step a while loop rather than an if?
  2. Why update the missing counter on == rather than >=?
  3. The overall complexity is O(n) because:





 Cheat sheet
Minimum window substring
Grow the window on the right until it contains everything, then shrink it from the left while it still does. The trick that keeps it O(n) is tracking a single count of unsatisfied characters rather than comparing two dictionaries on every step.
INTERVIEW · vizlearn.in/interview/minimum-window-substring.html
More in Interview
InterviewWhat is a Python list underneath?InterviewWhy does [[0]*3]*3 break?InterviewWhy is `in` slow on a list but fast on a set?InterviewTwo Sum
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact