Minimum Window Substring

Hard

#0076Time: O(m^3)Space: O(m + k)30 companies

Patterns

Sliding Window

Data structures

Hash Table String

Companies

Adobe Agoda Airbnb Amazon

Prompt

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 <= 10⁵
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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Create a frequency map tFreq for the string t.
1. Initialize minLength to a very large value and result to an empty string.
1. Iterate with a start pointer i from 0 to s.length() - 1.
1. Iterate with an end pointer j from i to s.length() - 1.
1. Extract the substring sub = s.substring(i, j + 1).
1. Check if sub is a valid window by creating a frequency map for sub and comparing it with tFreq.
1. If sub is valid and its length is less than minLength, update minLength and result.
1. Return result.

Walkthrough

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.

1class Solution {2    public String minWindow(String s, String t) {3        if (s.length() < t.length()) {4            return "";5        }6 7        Map<Character, Integer> tFreq = new HashMap<>();8        for (char c : t.toCharArray()) {9            tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);10        }11 12        int minLength = Integer.MAX_VALUE;13        String result = "";14 15        for (int i = 0; i < s.length(); i++) {16            for (int j = i; j < s.length(); j++) {17                String sub = s.substring(i, j + 1);18                if (sub.length() >= t.length()) {19                    if (containsAll(sub, tFreq)) {20                        if (sub.length() < minLength) {21                            minLength = sub.length();22                            result = sub;23                        }24                    }25                }26            }27        }28        return result;29    }30 31    private boolean containsAll(String sub, Map<Character, Integer> tFreq) {32        Map<Character, Integer> subFreq = new HashMap<>();33        for (char c : sub.toCharArray()) {34            subFreq.put(c, subFreq.getOrDefault(c, 0) + 1);35        }36 37        for (Map.Entry<Character, Integer> entry : tFreq.entrySet()) {38            char c = entry.getKey();39            int count = entry.getValue();40            if (subFreq.getOrDefault(c, 0) < count) {41                return false;42            }43        }44        return true;45    }46}

Complexity

Time

O(m^3)

Space

O(m + k)

Trade-offs

Pros

Simple to conceptualize and implement.

Cons

Extremely inefficient and will not pass the time limits for the given constraints.

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.

Algorithm

1. Create a frequency map tFreq for the string t.
1. Initialize minLength to a very large value and result to an empty string.
1. Iterate with a start pointer i from 0 to s.length() - 1.
1. Initialize an empty frequency map windowFreq.
1. Iterate with an end pointer j from i to s.length() - 1.
1. Add the character `s.charAt(j)` to `windowFreq`.
1. Check if `windowFreq` makes the window valid with respect to `tFreq`.
1. If the window is valid and its length is the smallest found so far, update the result.
1. Return result.

Walkthrough

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.

1class Solution {2    public String minWindow(String s, String t) {3        if (s.length() < t.length()) {4            return "";5        }6 7        Map<Character, Integer> tFreq = new HashMap<>();8        for (char c : t.toCharArray()) {9            tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);10        }11 12        int minLength = Integer.MAX_VALUE;13        String result = "";14 15        for (int i = 0; i < s.length(); i++) {16            Map<Character, Integer> windowFreq = new HashMap<>();17            for (int j = i; j < s.length(); j++) {18                char c = s.charAt(j);19                windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);20                21                if (j - i + 1 >= t.length()) {22                    if (isWindowValid(windowFreq, tFreq)) {23                        if (j - i + 1 < minLength) {24                            minLength = j - i + 1;25                            result = s.substring(i, j + 1);26                        }27                        // Optimization: Once a valid window is found for a starting 'i',28                        // any longer window starting at 'i' is not minimal.29                        break; 30                    }31                }32            }33        }34        return result;35    }36 37    private boolean isWindowValid(Map<Character, Integer> windowFreq, Map<Character, Integer> tFreq) {38        for (Map.Entry<Character, Integer> entry : tFreq.entrySet()) {39            char c = entry.getKey();40            int count = entry.getValue();41            if (windowFreq.getOrDefault(c, 0) < count) {42                return false;43            }44        }45        return true;46    }47}

Complexity

Time

O(m^2 * k)

Space

O(k)

Trade-offs

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.

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.

Algorithm

1. Create a frequency map tFreq for t.
1. Initialize left = 0, minLength = infinity, minStart = 0.
1. Initialize required = number of unique characters in t, and formed = 0.
1. Initialize a frequency map for the window, windowFreq.
1. Iterate right from 0 to s.length() - 1:
1. Add s[right] to the window and update windowFreq.
1. If s[right] is in tFreq and its count in windowFreq now equals its count in tFreq, increment formed.
1. While the window is valid (formed == required):
1. Update `minLength` and `minStart` if the current window is smaller.
1. Remove `s[left]` from the window by decrementing its count in `windowFreq`.

1If `s[left]` is in `tFreq` and its count just dropped below the required count, decrement `formed`.

1. Increment `left`.
1. After the loop, if minLength is still infinity, no such window exists. Otherwise, return the substring starting at minStart with length minLength.

Walkthrough

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.

1class Solution {2    public String minWindow(String s, String t) {3        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {4            return "";5        }6 7        Map<Character, Integer> tFreq = new HashMap<>();8        for (char c : t.toCharArray()) {9            tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);10        }11 12        int left = 0;13        int minLength = Integer.MAX_VALUE;14        int minStart = 0;15        int required = tFreq.size();16        int formed = 0;17 18        Map<Character, Integer> windowFreq = new HashMap<>();19 20        for (int right = 0; right < s.length(); right++) {21            char c = s.charAt(right);22            windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);23 24            if (tFreq.containsKey(c) && windowFreq.get(c).intValue() == tFreq.get(c).intValue()) {25                formed++;26            }27 28            while (left <= right && formed == required) {29                if (right - left + 1 < minLength) {30                    minLength = right - left + 1;31                    minStart = left;32                }33 34                char leftChar = s.charAt(left);35                windowFreq.put(leftChar, windowFreq.get(leftChar) - 1);36 37                if (tFreq.containsKey(leftChar) && windowFreq.get(leftChar).intValue() < tFreq.get(leftChar).intValue()) {38                    formed--;39                }40 41                left++;42            }43        }44 45        return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength);46    }47}

Complexity

Time

O(m + n)

Space

O(k)

Trade-offs

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).

Solutions

Solution

1public 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 ); } }

1class 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 ); } }

1class 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 ); } };

1''' >>> 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public 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 ); } }

1class 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 ); } }

1class 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 ); } };

1''' >>> 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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.