Find the shortest substring of s containing every character of t (with counts) using an expanding and shrinking sliding window in O(n). FAANG hard, run live.
The problem
Return the shortest substring of s that contains every character of t, including duplicates. Return "" if there is none.
Examples
Example 1
Input
min_window('ADOBECODEBANC', 'ABC')Expected output
'BANC'
Example 2
Input
min_window('a', 'a')Expected output
'a'
+ 4 hidden tests on Submit — needs two a's.
Edge cases to ask about
- t longer than s
- Duplicate characters in t
- Empty t
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Check every substring | O(n² · |t|) | O(|t|) | |
| bestExpand right, shrink left | O(n + |t|) | O(k) | missing counts characters still needed, so 'valid?' is an O(1) check. |
Walkthrough of the optimal approach (try it yourself first)
need holds how many of each character are still required, and missing is the total. Move end right; when a needed character arrives, decrement missing. Once missing == 0 the window is valid: record it, then move start right, putting characters back into need until the window becomes invalid again.
Both pointers only move forward, so the whole scan is O(n).
Complexity: O(n) time, O(k) space. Each index enters the window once (end) and leaves once (start); k is the alphabet size of the counts.
Reveal the reference solution
from collections import Counter def min_window(s, t): if not t or not s: return "" need = Counter(t) missing = len(t) start = best_start = 0 best_len = float("inf") for end, ch in enumerate(s): if need[ch] > 0: missing -= 1 need[ch] -= 1 while missing == 0: if end - start + 1 < best_len: best_start, best_len = start, end - start + 1 need[s[start]] += 1 if need[s[start]] > 0: missing += 1 start += 1 return "" if best_len == float("inf") else s[best_start:best_start + best_len]
Follow-ups interviewers ask
- Smallest window containing all DISTINCT characters of s.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Minimum Window Substring in Python?
The optimal solution runs in O(n) time and O(k) auxiliary space. Each index enters the window once (end) and leaves once (start); k is the alphabet size of the counts.
What is the brute-force approach, and how do you optimise it?
Check every substring: O(n² · |t|) time, O(|t|) space. Expand right, shrink left: O(n + |t|) time, O(k) space. `missing` counts characters still needed, so 'valid?' is an O(1) check.
What follow-up questions do interviewers ask about Minimum Window Substring?
Smallest window containing all DISTINCT characters of s.