Minimum Window Substring: How Do You Solve It?
Learn the sliding window approach to minimum window substring, its time complexity, and how to answer this interview question well.
Expected Interview Answer
Minimum window substring is solved with a variable-size sliding window and two hash maps: expand the right pointer until the window contains every required character with sufficient frequency, then contract the left pointer while the window stays valid, tracking the smallest valid window seen, giving O(n + m) time.
You first build a frequency map of the target string t, then slide a right pointer across s, decrementing a "still needed" counter each time a required character reaches its target count. Once the counter hits zero, the window fully covers t, so you greedily shrink from the left, recording the window length whenever it stays valid, and stop shrinking the instant a required character drops below its needed count. Each character enters and leaves the window at most once, so both pointers move monotonically forward, keeping the whole scan linear despite the nested-looking loops. The trick interviewers probe for is realizing contraction is not a second independent loop — it is amortized O(n) because the left pointer never resets.
- O(n + m) time using two pointers instead of brute-force O(n^2)
- O(k) space bounded by the alphabet of characters in t
- Left pointer only ever advances, keeping the scan linear
- Generalizes to many "smallest window containing X" problems
AI Mentor Explanation
A curator assembling the shortest highlight reel that contains at least one clip of every required shot type scrubs forward through raw footage, marking off shot types as soon as they appear. Once every required shot type has been captured on tape, the curator starts trimming from the front of the reel, cutting frames as long as every shot type is still represented somewhere inside. The moment trimming would remove the only copy of a required shot, the curator stops cutting from that end and resumes scrubbing forward for a replacement. This forward-scrub, then-trim rhythm is exactly the sliding window's expand-then-contract cycle, and it never rewinds the tape, which is why the whole search stays linear.
Step-by-Step Explanation
Step 1
Count target characters
Build a frequency map of t and set "required" to the number of distinct characters that must be matched.
Step 2
Expand the right pointer
Move right across s, updating a window frequency map; when a character's window count matches its target count, decrement "formed".
Step 3
Contract while valid
While formed equals required, record the window if it is the smallest so far, then shrink from the left, restoring counts as characters leave.
Step 4
Stop when right exhausts s
The best recorded window (or empty string if none was ever valid) is the answer.
What Interviewer Expects
- Explain why brute force is O(n^2 * m) and why the sliding window avoids it
- Track a "formed" counter rather than comparing full frequency maps every step
- Correctly handle duplicate characters in t (frequency, not just presence)
- State the final complexity as O(n + m) time and O(k) space
Common Mistakes
- Comparing entire hash maps on every step instead of using a formed/required counter
- Shrinking the window past validity before recording the current best length
- Forgetting duplicate characters need frequency counts, not just a seen-set
- Off-by-one errors when computing the final substring bounds
Best Answer (HR Friendly)
“I use two pointers to slide a window across the string: I grow the window until it contains everything I need, then I shrink it from the left as much as possible while it is still valid, keeping track of the smallest valid window I have seen. Because each pointer only ever moves forward, the whole thing runs in linear time even though it looks like nested loops.”
Code Example
from collections import Counter
def min_window(s, t):
if not s or not t:
return ""
need = Counter(t)
required = len(need)
window = {}
formed = 0
left = 0
best = (float("inf"), 0, 0)
for right, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right)
left_ch = s[left]
window[left_ch] -= 1
if left_ch in need and window[left_ch] < need[left_ch]:
formed -= 1
left += 1
length, start, end = best
return "" if length == float("inf") else s[start:end + 1]Follow-up Questions
- How would you modify this to find the minimum window containing at least k distinct characters?
- How would you return all minimum windows instead of just one?
- What changes if t can contain characters not present in s at all?
- How would you solve this if s and t were streamed rather than fully available upfront?
MCQ Practice
1. What is the time complexity of the sliding window solution to minimum window substring?
Each pointer moves forward at most n times total, and building the target frequency map is O(m), giving O(n + m).
2. What does the "formed" counter track in the standard solution?
formed counts how many distinct characters from t currently meet or exceed their required count inside the window.
3. Why does the left pointer never need to move backward?
Both pointers move monotonically forward across s, so total pointer movement is bounded by 2n, keeping the algorithm linear.
Flash Cards
What two data structures does minimum window substring use? — A frequency map for the target string t and a frequency map for the current window.
What triggers window contraction? — When the "formed" counter equals "required", meaning every needed character is satisfied.
What is the time complexity? — O(n + m), where n is the length of s and m is the length of t.
Why is the algorithm linear despite nested-looking loops? — The left and right pointers each move forward at most n times total, never resetting.