Minimum Window Substring Solution for Google
Company: Google · Difficulty: Hard · Topics: String, Hash Table, Sliding Window
Problem Statement
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
A substring is a contiguous sequence of characters within the string.
Examples
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window. The substring of s has length 1, so there is no window that includes both 'a's.
Example 4:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 5:
Input: s = "cabwefgewcwaefgcf", t = "cae"
Output: "cwae"
Explanation: The minimum window substring "cwae" includes 'c', 'a', and 'e' from string t.
Intuition
The key insight is to use a sliding window approach with two pointers. We expand the window to include all required characters, then contract it to find the minimum valid window. We use a hash table to track character frequencies.
Approach
Approach 1: Sliding Window (Optimal)
1. Use two pointers (left and right) to maintain a window
2. Expand the window by moving the right pointer until all characters from t are included
3. Contract the window by moving the left pointer to find the minimum valid window
4. Track character frequencies using hash tables
Approach 2: Optimized Sliding Window
1. Pre-filter string s to only include characters from t
2. Use the filtered array to find the minimum window
3. Map back to original string positions
Approach 3: Brute Force
1. Check all possible substrings of s
2. For each substring, verify if it contains all characters from t
3. Return the minimum valid substring
Dry Run
Let's trace through Example 1: s = "ADOBECODEBANC", t = "ABC"
Sliding Window Approach:
- Initialize: left=0, right=0, need={'A':1, 'B':1, 'C':1}, have={}
- right=0: s[0]='A', have={'A':1}, need={'A':0, 'B':1, 'C':1}
- right=1: s[1]='D', have={'A':1, 'D':1}, need={'A':0, 'B':1, 'C':1}
- right=2: s[2]='O', have={'A':1, 'D':1, 'O':1}, need={'A':0, 'B':1, 'C':1}
- right=3: s[3]='B', have={'A':1, 'D':1, 'O':1, 'B':1}, need={'A':0, 'B':0, 'C':1}
- right=4: s[4]='E', have={'A':1, 'D':1, 'O':1, 'B':1, 'E':1}, need={'A':0, 'B':0, 'C':1}
- right=5: s[5]='C', have={'A':1, 'D':1, 'O':1, 'B':1, 'E':1, 'C':1}, need={'A':0, 'B':0, 'C':0}
- All characters found! Window: "ADOBEC" (length=6)
- Contract: left=0, s[0]='A', can't remove 'A' (need it), left=1
- Continue contracting until we can't remove any more characters
- Final result: "BANC" (length=4)
Solution
Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.
Key Insights:
1. Sliding Window: Use two pointers to maintain a dynamic window
2. Character Counting: Track required and current character frequencies
3. Optimization: Contract the window as much as possible while maintaining validity
Edge Cases:
- Empty strings: return empty string
- Single character: check if it matches
- No valid window: return empty string
- Duplicate characters in t: must include all occurrences
Time Complexity
- Sliding Window: O(m + n) where m is length of s, n is length of t
- Optimized Sliding Window: O(m + n)
- Brute Force: O(m² * n)
Space Complexity
- Sliding Window: O(k) where k is the size of character set
- Optimized Sliding Window: O(k)
- Brute Force: O(m)