# Minimum Window Substring **Difficulty:** HARD [External](https://leetcode.com/problems/minimum-window-substring) Canonical: https://scaleengineer.com/dsa/problems/minimum-window-substring **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Data structures:** Hash Table, String **Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Infosys](https://scaleengineer.com/companies/infosys), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nagarro](https://scaleengineer.com/companies/nagarro), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Lyft](https://scaleengineer.com/companies/lyft), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [Snap](https://scaleengineer.com/companies/snap), [Apollo.io](https://scaleengineer.com/companies/apollo.io), [Fastenal](https://scaleengineer.com/companies/fastenal), [thoughtspot](https://scaleengineer.com/companies/thoughtspot) --- ## Problem 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**. **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. Since the largest window of s only has one 'a', return empty string. **Constraints:** * `m == s.length` * `n == t.length` * `1 <= m, n <= 105` * `s` and `t` consist of uppercase and lowercase English letters. **Follow up:** Could you find an algorithm that runs in `O(m + n)` time? # Approaches ## Brute Force Enumeration The most straightforward approach is to check every possible substring of `s`. For each substring, we verify if it contains all the characters from `t`. We keep track of the shortest such valid substring found. **Time:** O(m^3) · **Space:** O(m + k) **Pros:** Simple to conceptualize and implement. **Cons:** Extremely inefficient and will not pass the time limits for the given constraints. ### Explanation We generate all substrings of `s` using two nested loops, where `i` is the start index and `j` is the end index. For each substring, we create a frequency map of its characters. We also create a frequency map for the target string `t`. We then compare the two frequency maps. A substring is considered a valid "window" if the frequency of every character in `t` is less than or equal to its frequency in the substring. If a valid window is found, we compare its length with the minimum length found so far and update it if the current window is shorter. This process continues until all substrings have been checked. ```java class Solution { public String minWindow(String s, String t) { if (s.length() < t.length()) { return ""; } Map tFreq = new HashMap<>(); for (char c : t.toCharArray()) { tFreq.put(c, tFreq.getOrDefault(c, 0) + 1); } int minLength = Integer.MAX_VALUE; String result = ""; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { String sub = s.substring(i, j + 1); if (sub.length() >= t.length()) { if (containsAll(sub, tFreq)) { if (sub.length() < minLength) { minLength = sub.length(); result = sub; } } } } } return result; } private boolean containsAll(String sub, Map tFreq) { Map subFreq = new HashMap<>(); for (char c : sub.toCharArray()) { subFreq.put(c, subFreq.getOrDefault(c, 0) + 1); } for (Map.Entry entry : tFreq.entrySet()) { char c = entry.getKey(); int count = entry.getValue(); if (subFreq.getOrDefault(c, 0) < count) { return false; } } return true; } } ``` ### Algorithm - 1. Create a frequency map `tFreq` for the string `t`. - 2. Initialize `minLength` to a very large value and `result` to an empty string. - 3. Iterate with a start pointer `i` from `0` to `s.length() - 1`. - 4. Iterate with an end pointer `j` from `i` to `s.length() - 1`. - 5. Extract the substring `sub = s.substring(i, j + 1)`. - 6. Check if `sub` is a valid window by creating a frequency map for `sub` and comparing it with `tFreq`. - 7. If `sub` is valid and its length is less than `minLength`, update `minLength` and `result`. - 8. Return `result`. ## Optimized Brute Force This approach improves upon the pure brute force method by avoiding the repeated creation of frequency maps for overlapping substrings. Instead of recalculating the frequency map for each substring from scratch, we can build it incrementally. **Time:** O(m^2 * k) · **Space:** O(k) **Pros:** More efficient than the pure brute-force approach. **Cons:** Still inefficient for large inputs and results in a "Time Limit Exceeded" error on most platforms. ### Explanation We still use two nested loops to define the window, with `i` as the start and `j` as the end. For a fixed start `i`, we expand the window by moving `j` from `i` to the end of the string. As we expand the window one character at a time (by incrementing `j`), we update a single frequency map for the current window `s[i...j]`. At each step, we check if the current window is valid by comparing its frequency map with `t`'s frequency map. If a valid window is found, we record its length and check if it's the new minimum. ```java class Solution { public String minWindow(String s, String t) { if (s.length() < t.length()) { return ""; } Map tFreq = new HashMap<>(); for (char c : t.toCharArray()) { tFreq.put(c, tFreq.getOrDefault(c, 0) + 1); } int minLength = Integer.MAX_VALUE; String result = ""; for (int i = 0; i < s.length(); i++) { Map windowFreq = new HashMap<>(); for (int j = i; j < s.length(); j++) { char c = s.charAt(j); windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1); if (j - i + 1 >= t.length()) { if (isWindowValid(windowFreq, tFreq)) { if (j - i + 1 < minLength) { minLength = j - i + 1; result = s.substring(i, j + 1); } // Optimization: Once a valid window is found for a starting 'i', // any longer window starting at 'i' is not minimal. break; } } } } return result; } private boolean isWindowValid(Map windowFreq, Map tFreq) { for (Map.Entry entry : tFreq.entrySet()) { char c = entry.getKey(); int count = entry.getValue(); if (windowFreq.getOrDefault(c, 0) < count) { return false; } } return true; } } ``` ### Algorithm - 1. Create a frequency map `tFreq` for the string `t`. - 2. Initialize `minLength` to a very large value and `result` to an empty string. - 3. Iterate with a start pointer `i` from `0` to `s.length() - 1`. - 4. Initialize an empty frequency map `windowFreq`. - 5. Iterate with an end pointer `j` from `i` to `s.length() - 1`. - 6. Add the character `s.charAt(j)` to `windowFreq`. - 7. Check if `windowFreq` makes the window valid with respect to `tFreq`. - 8. If the window is valid and its length is the smallest found so far, update the result. - 9. Return `result`. ## Sliding Window with Frequency Maps The most efficient solution uses the sliding window technique. This approach maintains a "window" (a substring of `s`) using two pointers, `left` and `right`. The window is expanded by moving the `right` pointer and contracted by moving the `left` pointer. The goal is to find the smallest window that satisfies the condition. **Time:** O(m + n) · **Space:** O(k) **Pros:** Optimal time complexity.; Efficiently solves the problem within the given constraints. **Cons:** The logic can be tricky to implement correctly, with several conditions to track (window validity, character counts, pointer movements). ### Explanation First, we create a frequency map `tFreq` for the target string `t`. We also determine the number of unique characters in `t` that we need to find in a window, let's call this `required`. We use two pointers, `left` and `right`, both starting at the beginning of `s`. We also maintain a frequency map for the current window, `windowFreq`, and a counter `formed` which tracks how many of the required characters we have "formed" (i.e., their count in the window matches their count in `t`). We expand the window by incrementing the `right` pointer. For each new character added to the window, we update `windowFreq`. If adding this character causes its count to match the required count from `tFreq`, we increment `formed`. Once `formed` equals `required`, we have a valid window. Now, we try to make it smaller by contracting it from the left. We increment the `left` pointer. While contracting, we update the minimum length found so far. When removing a character from the left of the window, we update `windowFreq`. If this removal causes a character's count to drop below its required count, we decrement `formed`, and the window is no longer valid. We continue this process of expanding and contracting until the `right` pointer reaches the end of `s`. The smallest length recorded during the process gives us the minimum window substring. ```java class Solution { public String minWindow(String s, String t) { if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) { return ""; } Map tFreq = new HashMap<>(); for (char c : t.toCharArray()) { tFreq.put(c, tFreq.getOrDefault(c, 0) + 1); } int left = 0; int minLength = Integer.MAX_VALUE; int minStart = 0; int required = tFreq.size(); int formed = 0; Map windowFreq = new HashMap<>(); for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1); if (tFreq.containsKey(c) && windowFreq.get(c).intValue() == tFreq.get(c).intValue()) { formed++; } while (left <= right && formed == required) { if (right - left + 1 < minLength) { minLength = right - left + 1; minStart = left; } char leftChar = s.charAt(left); windowFreq.put(leftChar, windowFreq.get(leftChar) - 1); if (tFreq.containsKey(leftChar) && windowFreq.get(leftChar).intValue() < tFreq.get(leftChar).intValue()) { formed--; } left++; } } return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength); } } ``` ### Algorithm - 1. Create a frequency map `tFreq` for `t`. - 2. Initialize `left = 0`, `minLength = infinity`, `minStart = 0`. - 3. Initialize `required` = number of unique characters in `t`, and `formed = 0`. - 4. Initialize a frequency map for the window, `windowFreq`. - 5. Iterate `right` from `0` to `s.length() - 1`: - 6. Add `s[right]` to the window and update `windowFreq`. - 7. If `s[right]` is in `tFreq` and its count in `windowFreq` now equals its count in `tFreq`, increment `formed`. - 8. While the window is valid (`formed == required`): - 9. Update `minLength` and `minStart` if the current window is smaller. - 10. Remove `s[left]` from the window by decrementing its count in `windowFreq`. - 11. If `s[left]` is in `tFreq` and its count just dropped below the required count, decrement `formed`. - 12. Increment `left`. - 13. After the loop, if `minLength` is still infinity, no such window exists. Otherwise, return the substring starting at `minStart` with length `minLength`. # Solutions ### CSharp ```csharp public class Solution { public string MinWindow ( string s , string t ) { int [] need = new int [ 128 ]; int [] window = new int [ 128 ]; foreach ( var c in t ) { ++ need [ c ]; } int cnt = 0 , j = 0 , k = - 1 , mi = 1 << 30 ; for ( int i = 0 ; i < s . Length ; ++ i ) { ++ window [ s [ i ]]; if ( need [ s [ i ]] >= window [ s [ i ]]) { ++ cnt ; } while ( cnt == t . Length ) { if ( i - j + 1 < mi ) { mi = i - j + 1 ; k = j ; } if ( need [ s [ j ]] >= window [ s [ j ]]) { -- cnt ; } -- window [ s [ j ++]]; } } return k < 0 ? "" : s . Substring ( k , mi ); } } ``` ### Java ```java class Solution { public String minWindow ( String s , String t ) { int [] need = new int [ 128 ]; int [] window = new int [ 128 ]; int m = s . length (), n = t . length (); for ( int i = 0 ; i < n ; ++ i ) { ++ need [ t . charAt ( i )]; } int cnt = 0 , j = 0 , k = - 1 , mi = 1 << 30 ; for ( int i = 0 ; i < m ; ++ i ) { ++ window [ s . charAt ( i )]; if ( need [ s . charAt ( i )] >= window [ s . charAt ( i )]) { ++ cnt ; } while ( cnt == n ) { if ( i - j + 1 < mi ) { mi = i - j + 1 ; k = j ; } if ( need [ s . charAt ( j )] >= window [ s . charAt ( j )]) { -- cnt ; } -- window [ s . charAt ( j ++)]; } } return k < 0 ? "" : s . substring ( k , k + mi ); } } ``` ### CPP ```cpp class Solution { public: string minWindow ( string s , string t ) { int need [ 128 ]{}; int window [ 128 ]{}; int m = s . size (), n = t . size (); for ( char & c : t ) { ++ need [ c ]; } int cnt = 0 , j = 0 , k = - 1 , mi = 1 << 30 ; for ( int i = 0 ; i < m ; ++ i ) { ++ window [ s [ i ]]; if ( need [ s [ i ]] >= window [ s [ i ]]) { ++ cnt ; } while ( cnt == n ) { if ( i - j + 1 < mi ) { mi = i - j + 1 ; k = j ; } if ( need [ s [ j ]] >= window [ s [ j ]]) { -- cnt ; } -- window [ s [ j ++ ]]; } } return k < 0 ? "" : s . substr ( k , mi ); } }; ``` ### Python ```python ''' >>> deq = collections.deque([]) >>> deq.append(11) >>> deq.append(22) >>> deq.append(33) >>> >>> deq[0] 11 ''' import collections class Solution : def minWindow ( self , s : str , t : str ) -> str : cnt = 0 need = collections . Counter ( t ) start , end = len ( s ), 3 * len ( s ) # Arbitrary 3, just make sure end-start is larger than input s length, for later min-check d = {} # Using queue to store indexes, good for a large amount of API calls deq = collections . deque ([]) for i , c in enumerate ( s ): if c in need : deq . append ( i ) d [ c ] = d . get ( c , 0 ) + 1 # '=' also +1, because it's inceased already one line above :) if d [ c ] <= need [ c ]: cnt += 1 while deq and d [ s [ deq [ 0 ]]] > need [ s [ deq [ 0 ]]]: d [ s [ deq . popleft ()]] -= 1 if cnt == len ( t ) and deq [ - 1 ] - deq [ 0 ] < end - start : start , end = deq [ 0 ], deq [ - 1 ] return s [ start : end + 1 ] ############ from collections import Counter class Solution : def minWindow ( self , s : str , t : str ) -> str : ans = '' m , n = len ( s ), len ( t ) if m < n : return ans need = Counter ( t ) window = Counter () i , cnt , mi = 0 , 0 , inf for j , c in enumerate ( s ): window [ c ] += 1 if need [ c ] >= window [ c ]: # >= , because 1 line above already +=1 cnt += 1 while cnt == n : if j - i + 1 < mi : # in while mi = j - i + 1 ans = s [ i : j + 1 ] c = s [ i ] if need [ c ] >= window [ c ]: # char in window but not in need, need[c]=0, window[c]=1..2.. cnt -= 1 window [ c ] -= 1 i += 1 return ans ```