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.

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

Overview

Find the shortest substring containing every required character, including repeated requirements. A sliding window expands until it is valid, then contracts while it stays valid; frequency counts track what is still missing.

In this guide
  1. Run it: Minimum window substring in code
  2. The shape of the solution
  3. The grow-then-shrink shape
  4. The counter that makes it cheap
  5. Copies, and the empty cases
  6. Tracing "ADOBECODEBANC" with "ABC"
  7. The template this belongs to
  8. Edge cases
  9. Sources and next steps

Run it: Minimum window substring in code

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

1Python
Output
2Python
Output
3Python
Output

The shape of the solution

Expand the window's right edge until it is valid. Contains all of it 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 check 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 important. 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 on purpose. 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-in a row-sequence. A nested loop is not by itself quadratic.

The counter that makes it cheap

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

Copies, 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 check handle both "is this shorter" and "remember where it was". This 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 decides 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.

Sources and next steps

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

Shrink and expand a sliding window until it holds every character of t. Track character counts in a dictionary and record the smallest valid span.

INTERVIEW · vizlearn.in/interview/minimum-window-substring.html

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.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.