Minimum Window Substring

76.Minimum Window Substring

String

Hash Table

Sliding Window

Two Pointers

Problem Statement:

Given two strings s and t, return the minimum window substring of s that contains all characters in t. If there is no such substring, return the empty string "".

Example:

Input:

s = "ADOBECODEBANC"
t = "ABC"

→

Output:

"BANC"

Algorithm:

1. Use two arrays as frequency maps
2. Keep count of required characters
3. Expand window until valid substring found
4. Contract window to minimize length

Complexity:

Time: O(n) | Space: O(1) as we use fixed size arrays

Java Solution:

public String minWindow(String s, String t) {
    int i = 0, j = 0;
    // Count of characters still needed
    int count = t.length();
    
    // Frequency maps for both strings
    int[] sMap = new int[128];
    int[] tMap = new int[128];
    
    int min = Integer.MAX_VALUE;
    String res = "";
    
    // Build frequency map for pattern string
    for (char c : t.toCharArray()) 
        tMap[c]++;
    
    while (j < s.length()) {
        char c = s.charAt(j);
        
        // If character is needed, decrement count
        if (sMap[c]++ < tMap[c]) count--;
        
        // Try to minimize window when valid substring found
        while (count == 0) {
            int len = j - i + 1;
            if (len < min) {
                min = len;
                res = s.substring(i, j + 1);
            }
            
            // Update count if removing needed character
            c = s.charAt(i++);
            if (sMap[c]-- <= tMap[c]) count++;
        }
        
        j++;
    }
    
    return res;
}

Python Solution:

def minWindow(self, s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    # Dictionary to store character frequencies
    t_count = Counter(t)
    window = defaultdict(int)
    
    count = len(t)
    min_len = float('inf')
    res = ""
    i = 0
    
    for j, c in enumerate(s):
        # Add character to window
        window[c] += 1
        if c in t_count and window[c] <= t_count[c]:
            count -= 1
            
        # Try to minimize window when valid
        while count == 0:
            if j - i + 1 < min_len:
                min_len = j - i + 1
                res = s[i:j+1]
                
            # Remove character from window
            window[s[i]] -= 1
            if s[i] in t_count and window[s[i]] < t_count[s[i]]:
                count += 1
            i += 1
            
    return res

C++ Solution:

string minWindow(string s, string t) {
    vector<int> sMap(128), tMap(128);
    int count = t.length();
    int i = 0, j = 0;
    int min_len = INT_MAX;
    string res = "";
    
    // Build frequency map for pattern
    for (char c : t) tMap[c]++;
    
    while (j < s.length()) {
        // Add character to window
        if (sMap[s[j]]++ < tMap[s[j]]) count--;
        
        // Try to minimize window when valid
        while (count == 0) {
            if (j - i + 1 < min_len) {
                min_len = j - i + 1;
                res = s.substr(i, j - i + 1);
            }
            
            if (sMap[s[i]]-- <= tMap[s[i]]) count++;
            i++;
        }
        j++;
    }
    
    return res;
}