Minimum Window Substring
Find the shortest stretch of a string that contains every character of another string, counting repeats. The definitive variable-size sliding window problem. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Given two strings s and t, return the shortest contiguous substring of s that contains every character of t, including duplicates. If t has two as, the window needs at least two as. The characters don't have to appear in the same order as in t, and the window may contain extra characters.
If no substring of s works, return the empty string "". Matching is case-sensitive. Every test has at most one shortest window, so the answer is unique.
Aim for a solution that runs in O(|s| + |t|) time.
Example 1
- Input
- s = "XBYAZCAB", t = "ABC"
- Output
- "CAB"
"BYAZC" and "AZCAB" also contain A, B and C, but "CAB" at the end is shorter.
Example 2
- Input
- s = "baacb", t = "aab"
- Output
- "baa"
The window needs two a's and one b. "aacb" works too but is one character longer.
Example 3
- Input
- s = "a", t = "b"
- Output
- ""
Constraints
- 1 ≤ s.length, t.length ≤ 10⁵
- s and t contain only uppercase and lowercase English letters.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Minimum Window Substring in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Minimum Window Substring
Pattern: Variable-size sliding window with counts
"Shortest contiguous substring that satisfies a condition" is the classic sign of a sliding window. The condition here has a useful property: if a window contains all of t, any larger window around it does too. That monotonicity is what lets two pointers work.
Move the right edge forward until the window is valid (it covers t). Then move the left edge forward as long as it stays valid, recording the shortest valid window you see. When it stops being valid, go back to extending the right edge. Each pointer only moves forward, so the whole scan is linear.
The remaining question is how to check validity in O(1). Keep need[c], how many more of each character the window still needs, and a single counter missing of how many characters of t are still uncovered. Adding a character decrements need[c], and if it was positive, missing drops by one. The window is valid exactly when missing == 0.
Approach 1: Check every substring
For each start and end, count the characters in the substring and compare against the counts for t. It makes the condition concrete but is O(n²) substrings with O(n) or O(alphabet) work each.
Time O(n² · σ) for an alphabet of size σ · Space O(σ)
Approach 2: Fix each start, extend the end
For each start, grow the end while keeping running counts until the window covers t, then record its length. It avoids recounting, but every start can still scan to the end of the string.
Time O(n²) · Space O(σ)
Approach 3: Two-pointer sliding window
- Build
needfromtand setmissing = len(t). - For each
right: letc = s[right]. Ifneed[c] > 0, decrementmissing. Decrementneed[c](it can go negative, which means the window has a surplus). - While
missing == 0: if the window[left, right]is shorter than the best, record it. Then removes[left]: incrementneed[s[left]], and if it becomes positive, incrementmissing. Advanceleft. - Return the best window, or
""if none was found.
Characters that aren't in t just go negative and back, and never affect missing.
Time O(|s| + |t|) · Space O(σ)
| Approach | Time | Space |
|---|---|---|
| Check every substring | O(n² · σ) for an alphabet of size σ | O(σ) |
| Fix each start, extend the end | O(n²) | O(σ) |
| Two-pointer sliding window | O(|s| + |t|) | O(σ) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Minimum Window Substring solution in Python
def min_window(s: str, t: str) -> str:
need = Counter(t)
missing = len(t)
best_start, best_len = 0, len(s) + 1
left = 0
for right, c in enumerate(s):
if need[c] > 0:
missing -= 1
need[c] -= 1
while missing == 0:
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
out = s[left]
need[out] += 1
if need[out] > 0:
missing += 1
left += 1
return s[best_start:best_start + best_len] if best_len <= len(s) else ""Minimum Window Substring solution in JavaScript
function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
let missing = t.length;
let bestStart = 0;
let bestLen = Infinity;
let left = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
const count = need.get(c) ?? 0;
if (count > 0) missing--;
need.set(c, count - 1);
while (missing === 0) {
if (right - left + 1 < bestLen) {
bestStart = left;
bestLen = right - left + 1;
}
const out = s[left];
const outCount = need.get(out) + 1;
need.set(out, outCount);
if (outCount > 0) missing++;
left++;
}
}
return bestLen === Infinity ? '' : s.slice(bestStart, bestStart + bestLen);
}Common mistakes
- Tracking only which characters are present instead of how many, which fails when `t` has repeats like "aab".
- Decrementing `missing` for every matching character, including surplus copies, so the window looks valid too early.
- Checking validity by comparing two full count maps on every step, which adds an alphabet-sized factor.
- Recording the best window after shrinking past validity instead of before, which reports a window that no longer covers `t`.
- Building substrings inside the loop to compare lengths; store the start and length and slice once at the end.
What interviewers look for
Name the template first: "expand right until valid, shrink left while valid, record the best while it's valid." Then explain why it's correct: if a window starting at left is valid, no shorter window starting at left was skipped, because the right edge only moved as far as needed.
The missing counter is the detail interviewers listen for, since it turns an O(σ) validity check into O(1). Trace it on a case with a repeated character in t (like s = "baacb", t = "aab") to show surplus copies are handled.
Follow-up questions
How would you speed it up when s is much longer than t?
Pre-filter s to the list of (index, character) pairs whose character appears in t, and slide the window over that list instead. The window logic is identical, but the pointers skip irrelevant characters.
What if the characters of t must appear in order (as a subsequence)?
Then it is a different problem. For each place where t can be fully matched scanning forward, scan backward from the end to find the latest start that still contains t as a subsequence. That gives O(|s| · |t|), or use a DP over positions.
How would you find the longest window with at most k distinct characters?
Same two pointers, flipped goal: expand right, and while the window has more than k distinct characters, shrink from the left. Record the length whenever the window is valid. A count map plus its size tracks distinct characters in O(1).
Companies that ask Minimum Window Substring
Minimum Window Substring is tagged by 120 companies in our interview dataset. The score shows how often it comes up at each company.
- Illumina100%
- Wissen Technology100%
- Lyft94.3%
- PointClickCare94%
- Schneider Electric93%
- Snap91.8%
- Sofi91.4%
- Apolloio90.3%
- Mips Technologies90%
- Fis90%
- Snowflake89.9%
- Harness88.9%
- Dp World87.6%
- Thoughtspot87%
- Monzo84%
- Kaleidofin84%
- Bayer83%
- Endava83%
- Bonterra82%
- Diasorin82%
- Bigcommerce82%
- Zeta81.8%
- Moloco80.4%
- NXP Semiconductors80%
and 96 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required