Minimum Window Substring

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.

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

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.
Since the largest window of s only has one 'a', return empty string.

Note

If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution

The problem is similar to the problem here - [Find anagrams of a string in another string](find-anagrams-of-a-string-in-another-string).

The problem discussed in this article is a variation of the anagram problem. Instead of finding fixed-length anagram substrings, the goal is to find the minimum-length substring that contains all the characters of the anagram.

The ideal shortest solution would be an anagram of T as a substring of S. For example, if S = "adbacfab" and T = "abc", the answer is "bac", which is an anagram of T and a substring of S. However, consider S = "adobecodebanc" and T = "abc". Here, no anagram of T is a substring of S. Instead, we seek the smallest substring that contains all characters of T. For example, the substrings "adobec", "codeba", and "banc" all contain the characters of T, with "banc" being the minimum-length solution.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Brute Force Solution

The naive approach can be: a) Generate all substrings of string1 ("this is a test string"). b) Check if each substring contains all characters of string2 ("tist"). c) Print the smallest substring that includes all characters of string2.

Method 2 - Sliding Window (Using 2 Hashmaps and 2 pointers)

This problem is based on the variable-size sliding window pattern. We can use the sliding window strategy similar to the one discussed in the problem [Longest Substring with K Distinct Characters](longest-substring-with-k-distinct-characters).

Here is the approach:

Use two dictionaries to count the characters in t and the current window in s.
Expand the window by moving the end pointer.
Contract the window by moving the start pointer when the current window contains all characters of t.
Track the minimum window length and starting index.

Code

Java

class Solution {    
	public String minWindow(String s, String t) {  
	    int n = s.length();  
	  
	    // length of the minimum window substring (smallest substring of s that has all characters of t)  
	    int minLen = Integer.MAX_VALUE;  
	  
	    // start index of the minimum window substring  
	    int minStart = 0;  
	  
	    // stores the count of each character in the current window  
	    Map<Character, Integer> windowMap = new HashMap<>();  
	  
	    // stores the count of each character in the string t  
	    Map<Character, Integer> targetMap = new HashMap<>();  
	  
	    for(int i = 0; i < t.length(); i++) {  
	        char c = t.charAt(i);  
	        targetMap.put(c, targetMap.getOrDefault(c, 0)+1);  
	    }  
	  
	    int windowStart = 0;  
	    for(int windowEnd = 0; windowEnd < n; windowEnd++) {  
	        // Add the next character of the string to the window  
	        char c = s.charAt(windowEnd);  
	        windowMap.put(c, windowMap.getOrDefault(c, 0)+1);  
	  
	        // Keep looking for a smaller window while the current window substring contains all the characters of t  
	        while(containsAll(windowMap, targetMap)) {  
	            if(windowEnd-windowStart+1 < minLen) {  
	                minLen = windowEnd-windowStart+1;  
	                minStart = windowStart;  
	            }  
	  
	            // move the leftmost character out of the window  
	            char leftChar = s.charAt(windowStart);  
	            windowMap.put(leftChar, windowMap.get(leftChar)-1);  
	            if(windowMap.get(leftChar) == 0) {  
	                windowMap.remove(leftChar);  
	            }  
	            windowStart++; // shrink the window  
	        }  
	    }  
	  
	    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);  
	}  
	  
	private boolean containsAll(Map<Character, Integer> windowCharMap, Map<Character, Integer> substrMap) {  
	    for(Map.Entry<Character, Integer> entry : substrMap.entrySet()) {  
	        char c = entry.getKey();  
	        int count = entry.getValue();  
	  
	        if(!windowCharMap.containsKey(c)) {  
	            return false;  
	        }  
	  
	        if(windowCharMap.get(c) < count) {  
	            return false;  
	        }  
	    }  
	    return true;  
	}
}

Python

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)
        
        # length of the minimum window substring (smallest substring of s that has all characters of t)
        min_len = float('inf')
        
        # start index of the minimum window substring
        min_start = 0
        
        # stores the count of each character in the string t
        target_map = Counter(t)
        
        # stores the count of each character in the current window
        window_map = defaultdict(int)
        
        window_start = 0
        for window_end in range(n):
            # Add the next character of the string to the window
            char = s[window_end]
            window_map[char] += 1

            # Keep looking for a smaller window while the current window substring contains all the characters of t
            while self.contains_all(window_map, target_map):
                if window_end - window_start + 1 < min_len:
                    min_len = window_end - window_start + 1
                    min_start = window_start
                
                # Move the leftmost character out of the window
                left_char = s[window_start]
                window_map[left_char] -= 1
                if window_map[left_char] == 0:
                    del window_map[left_char]
                window_start += 1  # shrink the window
        
        return "" if min_len == float('inf') else s[min_start:min_start + min_len]
    
    def contains_all(self, window_map, target_map):
        for char, count in target_map.items():
            if window_map[char] < count:
                return False
        return True

Complexity

⏰ Time complexity: O(|S| + |T|)
- Reasoning: Each character in s is processed at most twice (once when added to the window and once when removed), and checking if the window contains all characters of t is O(1) due to the fixed alphabet size. Building the target map is O(|T|).
🧺 Space complexity: O(|S| + |T|)
- Reasoning: The window map can store up to all unique characters in s, and the target map stores all unique characters in t.