Minimum Window Substring
Problem
Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return an empty string.
- 1 ≤ s.length, t.length ≤ 10⁵
- s and t consist of English letters.
Example
s = "ADOBECODEBANC", t = "ABC""BANC"A brute-force approach would check every substring of s to see if it contains all characters of t, which is O(n^3) and infeasible for large inputs. The optimal approach uses a sliding window to expand and contract over s, tracking character counts to efficiently find the smallest valid window. Starting with pointers at the beginning, the window expands until it contains all characters of t. Then it contracts from the left to remove unnecessary characters, updating the minimum window length. This process repeats until the right pointer reaches the end of s. The critical insight is maintaining counts of required characters and only contracting when the window is valid, enabling an O(n) time solution.
Approach
Straightforward Solution
A brute-force approach enumerates all substrings of s and checks if each contains t, resulting in O(n^3) time due to substring generation and character counting, which is too slow.
Core Observation
The problem reduces to finding the smallest substring of s that contains all characters of t with correct multiplicities. This requires tracking character frequencies and efficiently checking window validity.
Path to Optimal
Recognizing the problem as a substring containment problem with multiplicities suggests a sliding window approach. By maintaining two hash maps—one for required character counts and one for the current window counts—and two pointers defining the window boundaries, the algorithm can expand the window to include all required characters and then contract it to find the minimal valid window. This approach reduces the complexity to O(n) because each character is visited at most twice (once when expanding and once when contracting).
Optimal Approach
Use a sliding window with two pointers. Expand the right pointer to include characters until the window contains all characters of t. Then, move the left pointer to shrink the window while maintaining validity. Keep track of the smallest window found. Return the substring corresponding to this window or an empty string if none exists.
Time
O(n)
Each character in s is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it. Hash map operations are O(1) on average, resulting in linear time complexity.
Space
O(m)
Auxiliary space is used for two hash maps storing character counts: one for t and one for the current window. The size of these maps is bounded by the number of unique characters in t, which is at most m = len(t). This space is necessary to track character frequencies.
Pattern Spotlight
Sliding Window (Variable Size with Frequency Counting)
When searching for a minimum or maximum substring containing all required elements, maintain counts of needed characters and expand the window until valid, then contract from the left to discard unnecessary characters, ensuring each character is processed at most twice.
Solution
| 1 | class Solution:
|
| 2 | def minWindow(self, s: str, t: str) -> str:
|
| 3 | if t == "":
|
| 4 | return ""
|
| 5 |
|
| 6 | count_t = {}
|
| 7 | for c in t:
|
| 8 | count_t[c] = 1 + count_t.get(c, 0)
|
| 9 |
|
| 10 | have, need = 0, len(count_t)
|
| 11 | res, res_len = [-1, -1], float("infinity")
|
| 12 | l = 0
|
| 13 | window = {}
|
| 14 |
|
| 15 | for r in range(len(s)):
|
| 16 | c = s[r]
|
| 17 | window[c] = 1 + window.get(c, 0)
|
| 18 |
|
| 19 | if c in count_t and window[c] == count_t[c]:
|
| 20 | have += 1
|
| 21 |
|
| 22 | while have == need:
|
| 23 | if (r - l + 1) < res_len:
|
| 24 | res = [l, r]
|
| 25 | res_len = (r - l + 1)
|
| 26 |
|
| 27 | window[s[l]] -= 1
|
| 28 | if s[l] in count_t and window[s[l]] < count_t[s[l]]:
|
| 29 | have -= 1
|
| 30 | l += 1
|
| 31 |
|
| 32 | l, r = res
|
| 33 | return s[l:r + 1] if res_len != float("infinity") else "" |
| 1 | class Solution { |
| 2 | public String minWindow(String s, String t) { |
| 3 | if (t.isEmpty()) { |
| 4 | return ""; |
| 5 | } |
| 6 | |
| 7 | Map<Character, Integer> countT = new HashMap<>(); |
| 8 | for (char c : t.toCharArray()) { |
| 9 | countT.put(c, 1 + countT.getOrDefault(c, 0)); |
| 10 | } |
| 11 | |
| 12 | int have = 0; |
| 13 | int need = countT.size(); |
| 14 | int[] res = {-1, -1}; |
| 15 | int resLen = Integer.MAX_VALUE; |
| 16 | int l = 0; |
| 17 | Map<Character, Integer> window = new HashMap<>(); |
| 18 | |
| 19 | for (int r = 0; r < s.length(); r++) { |
| 20 | char c = s.charAt(r); |
| 21 | window.put(c, 1 + window.getOrDefault(c, 0)); |
| 22 | |
| 23 | if (countT.containsKey(c) && window.get(c).intValue() == countT.get(c).intValue()) { |
| 24 | have++; |
| 25 | } |
| 26 | |
| 27 | while (have == need) { |
| 28 | if ((r - l + 1) < resLen) { |
| 29 | res[0] = l; |
| 30 | res[1] = r; |
| 31 | resLen = r - l + 1; |
| 32 | } |
| 33 | |
| 34 | char leftChar = s.charAt(l); |
| 35 | window.put(leftChar, window.get(leftChar) - 1); |
| 36 | if (countT.containsKey(leftChar) && window.get(leftChar) < countT.get(leftChar)) { |
| 37 | have--; |
| 38 | } |
| 39 | l++; |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | return resLen == Integer.MAX_VALUE ? "" : s.substring(res[0], res[1] + 1); |
| 44 | } |
| 45 | } |
Step-by-Step Solution
Build Frequency Map for Target String and Initialize Sliding Window State
| 6 | count_t = {}
|
| 7 | for c in t:
|
| 8 | count_t[c] = 1 + count_t.get(c, 0)
|
| 10 | have, need = 0, len(count_t)
|
| 11 | res, res_len = [-1, -1], float("infinity")
|
| 12 | l = 0
|
| 13 | window = {}
|
Objective
To count the frequency of each character in t and set up variables to track the sliding window and result.
Key Insight
Counting the required characters upfront allows the algorithm to know exactly when the window contains all needed characters. Initializing counters for how many unique characters have been satisfied ('have') versus how many are needed ('need') enables efficient validity checks. The window map tracks the current counts of characters in the sliding window, and the result variables store the best window found so far.
Interview Quick-Check
Core Logic
Building a frequency map for t enables constant-time checks of whether the current window meets the required character counts.
State & Boundaries
Initialize 'have' to 0 and 'need' to the number of unique characters in t to track window validity.
Common Pitfalls & Bugs
Forgetting to initialize the window map or result variables correctly can lead to incorrect window tracking or failure to update the minimal window.
Expand the Window by Moving Right Pointer and Update Counts
| 15 | for r in range(len(s)):
|
| 16 | c = s[r]
|
| 17 | window[c] = 1 + window.get(c, 0)
|
| 19 | if c in count_t and window[c] == count_t[c]:
|
| 20 | have += 1
|
Objective
To iterate over s with the right pointer, expanding the window and updating character counts to track when the window satisfies the requirements.
Key Insight
As the right pointer moves, characters are added to the window map. When the count of a character in the window matches the required count in t, the 'have' counter increments, indicating one more required character is fully satisfied. This incremental tracking avoids rechecking the entire window for validity, enabling efficient detection of valid windows.
Interview Quick-Check
Core Logic
Incrementing the count of the current character and updating 'have' only when the count matches the required frequency ensures accurate tracking of window validity.
State & Boundaries
The right pointer iterates over all characters in s, expanding the window one character at a time.
Common Pitfalls & Bugs
Failing to check if the character is in the target frequency map before updating 'have' can cause incorrect validity tracking.
Contract the Window by Moving Left Pointer to Find Minimum Valid Substring
| 22 | while have == need:
|
| 23 | if (r - l + 1) < res_len:
|
| 24 | res = [l, r]
|
| 25 | res_len = (r - l + 1)
|
| 27 | window[s[l]] -= 1
|
| 28 | if s[l] in count_t and window[s[l]] < count_t[s[l]]:
|
| 29 | have -= 1
|
| 30 | l += 1
|
Objective
To shrink the window from the left while it remains valid, updating the result with the smallest window found.
Key Insight
Once the window contains all required characters ('have' == 'need'), the algorithm attempts to minimize the window size by moving the left pointer forward. Decreasing the count of the leftmost character may invalidate the window if it falls below the required count, so 'have' is decremented accordingly. This careful contraction ensures the minimal valid window is found without missing any potential smaller windows.
Interview Quick-Check
Core Logic
Contracting the window while maintaining validity and updating the minimal window length ensures the algorithm finds the smallest substring containing all characters.
State & Boundaries
The while loop continues as long as the window is valid, allowing progressive shrinking from the left.
Common Pitfalls & Bugs
Not updating 'have' when the count of a character falls below the required frequency leads to incorrect window validity checks.
Return the Minimum Window Substring or Empty String if None Found
| 32 | l, r = res
|
| 33 | return s[l:r + 1] if res_len != float("infinity") else "" |
Objective
To extract and return the substring corresponding to the smallest valid window found, or return an empty string if no valid window exists.
Key Insight
After processing the entire string, the result indices represent the boundaries of the minimal window. If no valid window was found, the result length remains infinity, and an empty string is returned. This final step translates the indices into the required output format.
Interview Quick-Check
Core Logic
Returning the substring using the stored indices ensures the correct minimal window is output.
State & Boundaries
Check if the result length is still infinity to determine if a valid window was found.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
have, need = 0, len(count_t)Initialize 'have' and 'need' counters for window validity.
'have' tracks how many unique characters currently meet required counts, while 'need' is the total unique characters needed; this enables efficient validity checks.
if c in count_t and window[c] == count_t[c]:Check if current character count matches required count in t.
Only when the window count equals the required count for a character does it contribute to satisfying the overall requirement, so this condition triggers incrementing 'have'.
while have == need:While the window is valid, attempt to contract it from the left.
Contracting the window when valid helps find the minimal window containing all required characters by removing unnecessary characters from the left.
if s[l] in count_t and window[s[l]] < count_t[s[l]]:Check if the removed character is required and if its count falls below required.
If the count of a required character falls below its needed frequency, the window is no longer valid, so 'have' must be decremented.
count_t = {}Initialize a dictionary to count characters in t.
This data structure is essential for tracking the required frequency of each character, enabling constant-time lookups during window expansion.
count_t[c] = 1 + count_t.get(c, 0)Increment the count of the current character in count_t.
Accurately tracking the frequency of each character in t is critical for validating window contents later.
window = {}Initialize a dictionary to count characters in the current window.
Tracking the frequency of characters in the current window is necessary to compare against required counts and determine window validity.
window[c] = 1 + window.get(c, 0)Increment the count of the current character in the window.
Updating the window's character counts allows tracking how many times each character appears, which is essential for validity checks.
have += 1Increment 'have' when a required character's count is met.
Tracking how many unique characters meet their required counts enables quick checks of window validity without scanning all characters.
window[s[l]] -= 1Decrease the count of the character at the left pointer in the window.
Removing the leftmost character from the window updates counts to reflect the contracted window, which may invalidate the window if counts fall below requirements.
have -= 1Decrement 'have' when window no longer satisfies a required character count.
Maintaining accurate 'have' count ensures the algorithm knows when the window loses validity, preventing incorrect minimal window updates.
return s[l:r + 1] if res_len != float("infinity") else ""Return the minimal window substring or empty string if none found.
This final step produces the required output, returning the minimal valid substring or empty string if no valid window exists.
if t == "":Return an empty string if t is empty.
An empty target string means no characters are required, so the minimal window is trivially empty; this early return handles this edge case efficiently.
res, res_len = [-1, -1], float("infinity")Initialize result indices and minimal window length.
Storing the best window found so far allows updating the result when smaller valid windows are discovered.
for r in range(len(s)):Iterate over s with the right pointer to expand the window.
The right pointer moves forward to include new characters, enabling exploration of all possible windows.
if (r - l + 1) < res_len:Check if current window length is smaller than the best found.
Updating the result only when a smaller valid window is found ensures the minimal window is recorded.
res = [l, r]Update result indices to current window boundaries.
Storing the current minimal window boundaries allows returning the correct substring at the end.
res_len = (r - l + 1)Update the minimal window length to current window size.
Tracking the smallest window length found so far is necessary to compare future windows and maintain the minimal result.
l += 1Move the left pointer forward to contract the window.
Advancing the left pointer shrinks the window, enabling the search for smaller valid windows.
return ""Return immediately with empty string for empty t.
This prevents unnecessary computation when the target is empty, ensuring correctness and efficiency.
for c in t:Iterate over each character in t to build frequency map.
Counting each character's occurrences in t is necessary to know the exact requirements for a valid window.
l = 0Initialize left pointer of the sliding window.
The left pointer marks the start of the current window and moves forward to contract the window when possible.
c = s[r]Get the current character at the right pointer.
Accessing the current character is necessary to update window counts and check validity.
l, r = resUnpack the result indices into left and right boundaries.
Extracting the stored indices prepares for substring extraction or empty string return.
Test Your Understanding
Why does the algorithm only contract the window when it contains all required characters, and how does this ensure the minimal window is found?
Contracting the window only when it contains all required characters ensures the window remains valid. By shrinking from the left, the algorithm discards unnecessary characters, progressively finding smaller valid windows. This process guarantees that the minimal window containing all characters of t is found because any smaller window would exclude a required character, invalidating the window.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Minimum Window Substring from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Window Substring drill