Minimum Window Substring
Asked at Amazon, Microsoft, Oracle, Walmart
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.
Asked At
| 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.
Visual walkthrough for s = "ADOBECODEBANC", t = "ABC":
Target: {A:1, B:1, C:1}, formed = 0, needed = 3
- Expand right=0: A. window={A:1}. A needs 1, got 1 -> formed=1
- Expand right=1: D. window={A:1,D:1}. formed=1
- Expand right=2: O. window={A:1,D:1,O:1}. formed=1
- Expand right=3: B. window={A:1,D:1,O:1,B:1}. formed=2
- Expand right=4: E. formed=2
- Expand right=5: C. window={A:1,D:1,O:1,B:1,E:1,C:1}. formed=3! Valid window!
- Contract left=0 to 1: remove A. formed drops to 2. Invalid. Min="ADOBEC" (len 6)
- Continue expanding and contracting... eventually find "BANC" (len 4)
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.