Minimum Window Substring
Expand to satisfy the requirement, then contract to minimize.
Sliding Window Trace
Problem
Given two strings s and t, find the shortest contiguous part of s that contains all characters from t with the required multiplicities. Return the empty string if no substring can satisfy the requirement.
Examples
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
BANC contains A, B, and C, and no shorter valid window exists.Input: s = "a", t = "aa"
Output: ""
a, but two are required.The Goal
Find the shortest stretch of s that contains every character of t, repeats included. Extra characters are fine. If no stretch works, return "".
For t = "ABC", you need one A, one B and one C. ADOBEC qualifies, extra letters and all. For t = "AABC", you'd need two As.
Every count has to be met
A window is valid when it holds at least as many of each character as t does. Extras don't hurt.
Expand, Then Contract
Move right until the window covers t. Then move left for as long as it still covers t, recording each window on the way. When it stops covering t, go back to moving right.
The shortest window turns up while shrinking. After ADOBEC, dropping the A breaks it, so right has to find another A.
Move right until every required character is in.
Read through ADOBEC to cover ABC.
Counting What's Missing
need holds the counts from t, and window holds the counts in the current stretch. missing starts at len(t). It drops when an incoming character fills a count that's still short, and rises when a dropped character leaves one short.
need = frequency(t)
left = 0, missing = length(t)
best = empty
for right from 0 to length(s) - 1:
add s[right] and update missing
while missing == 0:
record the smallest valid window
remove s[left] and update missing
left += 1
return bestmissing == 0 tells you the window is valid without rescanning it.
| State | Meaning | For t = "ABC" |
|---|---|---|
| need | Counts in t | A: 1, B: 1, C: 1 |
| window | Counts in the window | What the window covers now |
| missing | Required characters not yet covered | 3 at the start, 0 when valid |
Walkthrough
Run it on ADOBECODEBANC with t = "ABC".
right reaches the C at 5, and ADOBEC covers t: length 6. Dropping its A breaks it. The next A, at 10, makes the window valid again, and it shrinks to CODEBA, still length 6.
Then the last C arrives. ODEBANC shrinks past O, D and E to BANC, length 4. That's the answer.
Checkpoint · predict the next step
Step 11 of 35 on the stage: Take 'D' at 7. t has no 'D', so missing stays 1.
window "DOBECOD" (left 1, right 7) · missing 1 · best "ADOBEC"
Pitfalls
- Growing without shrinking finds a valid window, not the shortest. With
s = "BA"andt = "A", you'd stop atBAinstead ofA. - Shrink with
while, notif. One step ofrightcan free several letters. - Record before you drop the left character.
- An extra copy isn't a shortfall. Only
window[ch] < need[ch]raisesmissing.
What should happen as soon as the window becomes valid?
Complexity
There's a while inside the for, but both pointers only move forward. Each character enters the window once and leaves at most once, so time is O(|s| + |t|), counting the pass that builds need.
The maps hold one count per character, so space is O(alphabet), which is constant for a fixed alphabet.
Two forward pointers
- Build need from tOne count per character of t.O(|t|)
- Expand with rightEach character enters once.dominantO(n)
- Contract with leftEach character leaves at most once.dominantO(n)
- Frequency mapsConstant for a fixed alphabet.O(alphabet)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear, because neither pointer ever moves back.
In short
Count the characters you need. Expand the right edge until the window contains all of them, then contract the left edge as far as possible while still valid, recording the smallest such window. A 'need' counter lets you check validity in O(1) per step.
Common mistake
Only expanding, never contracting — the minimum window requires shrinking whenever the constraint is still met.