76. Minimum Window Substring
Asked at Amazon, Microsoft, Oracle, Walmart
Difficulty
Hard
Time
O(m + n)
Space
O(k)
Pattern
Hash Table
Companies
4
Problem
You are given two strings: a long string s and a short string t. Your job is to find the smallest substring of s that contains every character of t.
"Contains every character" means with the right counts. If t has two 'a's, the window must also have at least two 'a's. The characters do not need to appear in the same order as in t.
Return that smallest substring. If no substring of s can hold all of t, return the empty string "". The test data is built so that only one smallest window exists.
Find the shortest window holding A, B, C
Constraints
- ●
1 <= s.length, t.length <= 10^5 - ●
s and t contain only uppercase and lowercase English letters - ●
The answer is guaranteed to be unique when it exists
Examples
s = "ADOBECODEBANC", t = "ABC""BANC"s = "a", t = "a""a"s = "a", t = "aa"""Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Oracle | Hard | View all Oracle questions → |
| Walmart | Hard | View all Walmart questions → |
How to Think About It
Brute force: generate every substring of s and check if it contains all characters of t. Check each substring with a frequency count. That's O(n³) -- way too slow.
Key insight: use two pointers (left and right) to maintain a window. Expand right to include characters. When the window contains all of t's characters, contract left to shrink the window while still maintaining the condition. Track the minimum window found.
Data structure: use two hash maps -- one for t's character frequencies (target), and one for the current window's character frequencies (window). Or use a single hash map with positive/negative counts to track how many characters are still needed.
The "formed" counter: instead of comparing two hash maps every time, maintain a formed counter that tracks how many unique characters have reached their required frequency. When formed equals the number of unique characters in t, the window is valid.
Edge cases: s shorter than t is impossible (return ""). t has duplicate characters -- the window must contain at least that many. All characters of t are the same. s has only one valid window.
Optimal Approach
Step 1: Build a frequency hash map for t (target counts).
Step 2: Initialize left=0, right=0, formed=0, needed=number of unique chars in t.
Step 3: Expand the window by moving right. For each character at right:
- Increment its count in the window map
- If the window count equals the target count for that character, increment
formed
Step 4: Whenformed==needed, the window is valid. Contract from left: - Record the minimum window if current is smaller
- Decrement the count of the character at left
- If the count drops below the target, decrement
formed - Move left forward
Step 5: Repeat until right reaches the end of s.
Walkthrough for s="ADOBECODEBANC", t="ABC":
- Target: {A:1, B:1, C:1}, needed=3
- After expansion to index 5: window="ADOBEC", formed=3. Min="ADOBEC" (6)
- Contract: left moves to 1, window="DOBEC", formed=2 (lost A)
- Expand to find A again... eventually find "BANC" (4)
Time: O(n) where n is length of s. Each character is visited at most twice (once by right, once by left). Space: O(k) where k is the character set size.
Grow right, shrink left
What Trips People Up in Real Interviews
Using a single hash map with positive/negative counts instead of two hash maps. The single-map approach uses positive counts for needed characters and negative for surplus. It works but is harder to explain under pressure. Two maps are clearer for interviews.
Forgetting to check if formed == needed AFTER expanding the window. Many candidates check this condition at the wrong time, recording windows that don't actually contain all characters of t.
Not shrinking the window enough. After finding a valid window, you must keep shrinking from the left as long as the window remains valid. Stopping too early misses the minimum window.
Confusing "contains all characters" with "contains all unique characters". The window must contain at least the frequency of each character in t, not just one of each. If t = "AA", the window must have at least 2 A's.
Off-by-one in recording the minimum window. The window length is right - left + 1 (inclusive), not right - left. Getting this wrong gives incorrect window boundaries even if the logic is otherwise correct.
Solution Code
O(m + n) timedef minWindow(s, t):
from collections import Counter
if not t or not s:
return ""
target = Counter(t)
needed = len(target)
window = {}
formed = 0
left = 0
min_len = float('inf')
min_left = 0
for right, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in target and window[ch] == target[ch]:
formed += 1
while formed == needed:
if right - left + 1 < min_len:
min_len = right - left + 1
min_left = left
window[s[left]] -= 1
if s[left] in target and window[s[left]] < target[s[left]]:
formed -= 1
left += 1
return "" if min_len == float('inf') else s[min_left:min_left + min_len]Frequently Asked Questions
What is the Minimum Window Substring problem?
Given two strings s and t, find the minimum window in s that contains all characters of t (including duplicates). If no such window exists, return an empty string. This is a classic `sliding window` problem that tests your ability to manage frequency counts and window expansion/contraction.
How do you solve Minimum Window Substring?
The optimal approach runs in O(m + n) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Window Substring?
Minimum Window Substring is asked at Amazon, Microsoft, Oracle, Walmart. It is a hard difficulty problem.
What are common mistakes on Minimum Window Substring?
- Using a single `hash map` with positive/negative counts instead of two `hash maps`. The single-map approach uses positive counts for needed characters and negative for surplus. It works but is harder to explain under pressure. Two maps are clearer for interviews.
- Forgetting to check if `formed` == `needed` AFTER expanding the window. Many candidates check this condition at the wrong time, recording windows that don't actually contain all characters of t.
- Not shrinking the window enough. After finding a valid window, you must keep shrinking from the left as long as the window remains valid. Stopping too early misses the minimum window.
- Confusing "contains all characters" with "contains all unique characters". The window must contain at least the frequency of each character in t, not just one of each. If t = "AA", the window must have at least 2 A's.
- Off-by-one in recording the minimum window. The window length is `right - left + 1` (inclusive), not `right - left`. Getting this wrong gives incorrect window boundaries even if the logic is otherwise correct.