Minimum Window Substring [Sliding Window]

Sliding Window Hard

Python Java C++

def minWindow(s: str, t: str) -> str:
    # Initialize frequency maps for window and pattern
    sMap = [0] * 128
    tMap = [0] * 128
    i = j = 0
    minLen = float('inf')
    res = ""
    
    # Build pattern frequency map
    for c in t:
        tMap[ord(c)] += 1
    
    # Initialize count to track required characters
    count = len(t)
    
    # Process each character using sliding window
    while j < len(s):
        c = ord(s[j])
        
        # If adding character helps match pattern, decrement count
        if sMap[c] < tMap[c]:
            count -= 1
        sMap[c] += 1
        
        # While window contains pattern, try to minimize
        while count == 0:
            currLen = j - i + 1
            
            # Update result if current window smaller
            if currLen < minLen:
                minLen = currLen
                res = s[i:j+1]
            
            # Remove leftmost character
            c = ord(s[i])
            if sMap[c] <= tMap[c]:
                count += 1
            sMap[c] -= 1
            i += 1
            
        j += 1
        
    return res

class Solution {
    public String minWindow(String s, String t) {
        int i = 0, j = 0;
        int[] sMap = new int[128];
        int[] tMap = new int[128];
        int min = Integer.MAX_VALUE;
        String res = "";
        
        // Count map represents amount of each in pattern
        for (char c : t.toCharArray()) 
            tMap[c]++;
        
        // Init count to num characters in P
        int count = t.length();
  
        while (j < s.length()) {
            char c = s.charAt(j);
            
            // Adding a new letter, if we need more of this letter, decrement count
            if (sMap[c]++ < tMap[c]) count--;
            
            while (count == 0) {
                int len = j - i + 1;

                if (len < min) {
                    min = len;
                    res = s.substring(i, j + 1);
                }

                //if we find the window's size equals to p, then we have to move i (narrow the window) to find the new match window
                //++ to reset the hash because we kicked out the left
                //only increase the count if the character is in p
                c = s.charAt(i++);
                if(sMap[c]-- <= tMap[c]) count++;  
            }

            j++;
        }
        return res; 
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        // Initialize frequency maps for window and pattern
        vector sMap(128, 0);
        vector tMap(128, 0);
        int i = 0, j = 0;
        int minLen = INT_MAX;
        string res = "";
        
        // Build pattern frequency map
        for (char c : t)
            tMap[c]++;
        
        // Initialize count to track required characters
        int count = t.length();
        
        // Process each character using sliding window
        while (j < s.length()) {
            char c = s[j];
            
            // If adding character helps match pattern, decrement count
            if (sMap[c]++ < tMap[c])
                count--;
            
            while (count == 0) {
                int currLen = j - i + 1;
                
                if (currLen < minLen) {
                    minLen = currLen;
                    res = s.substr(i, currLen);
                }
                
                c = s[i++];
                if (sMap[c]-- <= tMap[c])
                    count++;
            }
            
            j++;
        }
        
        return res;
    }
};

Problem Statement

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

Detailed Explanation

Approach

This solution uses a sliding window approach with character frequency counting. The key insight is using two frequency maps and a count variable to efficiently track when all required characters are present in the current window.

Key Concepts

1. Frequency Maps: Track character counts in both pattern and window
2. Required Count: Track number of characters still needed
3. Window Optimization: Minimize window when valid pattern found
4. Character Array: Use array instead of map for O(1) lookups

Algorithm Steps

1. Initialize tracking structures:
   • Array for window character frequencies
   • Array for pattern character frequencies
   • Count variable for total required characters
2. Process string using sliding window:
   • Add characters and update count when needed
   • When pattern matched, try to minimize window
   • Remove characters from start while window valid
3. Track minimum valid window found

Time and Space Complexity

• Time Complexity: O(m + n)
  • m is length of source string
  • n is length of pattern string
  • Each character processed at most twice
• Space Complexity: O(1)
  • Fixed size arrays for character frequencies
  • Only storing result string

Why This Works

The solution is efficient because:

• Character Counting:
  • Frequency arrays give O(1) lookup
  • No need for hash map overhead
  • Works with all ASCII characters
• Count Variable:
  • Avoids checking pattern match each time
  • Updates incrementally with window changes
  • O(1) valid window check
• Window Shrinking:
  • Only shrinks when window is valid
  • Guarantees minimum window found
  • No unnecessary comparisons

Edge Cases

• Empty strings: Return empty string
• Pattern longer than string: Return empty string
• Single character pattern: Return minimal window containing character
• Pattern with duplicates: Must match frequency of duplicates
• No valid window: Return empty string

Common Mistakes

• Not handling character frequencies correctly
• Incorrect count updates when removing characters
• Not checking window validity properly
• Using hash map instead of array for frequencies
• Incorrect window length calculation