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 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.

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.

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.

Run it in Python

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.

min_window.pyPython 3
Output
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