Leetcode 76. Minimum Window Substring

Let's understand what we're being asked to do. We have two strings: s = "ADOBECODEBANC" (the main string) and t = "ABC" (the target characters we need to find).

We need to find the smallest substring of s that contains all characters from t. In this example, "BANC" is the answer because it contains 'A', 'B', and 'C', and no shorter substring does.

Important constraint: If t has duplicate characters like "AABC", our substring must contain at least that many duplicates. So "ABC" wouldn't work - we'd need at least two 'A's.

Edge cases to consider: What if no valid substring exists? (return ""). What if t is longer than s? What if s itself is the minimum window? What if multiple windows have the same minimum length?

The brute force approach generates all possible substrings of s and checks each one to see if it contains all characters from t (with correct frequencies). For each starting position, we expand to every possible ending position, checking character counts at each step. This requires nested loops and repeated character counting, making it highly inefficient for large inputs.

def min_window_substring(s, t):
    """
    Brute force approach: Generate all substrings and check each one.
    For each starting position, expand to every ending position.
    Check if substring contains all characters from t with correct frequencies.
    """
    if not s or not t:
        return ""
    
    # Count frequency of characters in t
    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1
    
    min_length = float('inf')
    result = ""
    
    # Try every starting position
    for start in range(len(s)):
        # Try every ending position from start
        for end in range(start, len(s)):
            # Extract substring
            substring = s[start:end + 1]
            
            # Count frequency of characters in substring
            sub_freq = {}
            for char in substring:
                sub_freq[char] = sub_freq.get(char, 0) + 1
            
            # Check if substring contains all characters from t
            is_valid = True
            for char in t_freq:
                if sub_freq.get(char, 0) < t_freq[char]:
                    is_valid = False
                    break
            
            # Update result if valid and shorter
            if is_valid and len(substring) < min_length:
                min_length = len(substring)
                result = substring
    
    return result

We need to track two things simultaneously: whether our current window contains all required characters, and whether we can shrink it while still maintaining coverage.

As we expand our window to the right, we're looking for coverage. Once we have all characters, we try to shrink from the left to find the minimum size.

Instead of checking every possible substring (which would be O(n²) or worse), we can use a two-pointer approach where the window expands and contracts dynamically.

This transforms an exponential problem into a linear one - we only pass through the string once with each pointer!

Imagine you're looking through a telescope with adjustable zoom. You start zoomed out (wide window) until you can see all the targets you need. Then you zoom in (shrink window) as much as possible while keeping all targets visible.

The key insight: once you've found a valid window, you don't need to restart from scratch - just slide the left edge forward until the window becomes invalid, then continue expanding the right edge. This sliding motion is what makes it efficient.

The optimal approach uses a sliding window with two pointers and frequency maps. First, build a frequency map of characters in t. Then expand the right pointer to grow the window until all required characters are covered. Once covered, shrink from the left to find the minimum valid window, tracking the smallest one found. Continue this expand-shrink cycle through the entire string, maintaining character counts to know when the window is valid.

def min_window_substring(s, t):
    """
    Find the smallest substring of s that contains all characters of t.
    Uses sliding window with frequency maps.
    """
    # Edge case: if t is longer than s, no solution exists
    if len(t) > len(s):
        return ""
    
    # Build frequency map for target string t
    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1
    
    # Initialize window state
    required = len(t_freq)  # Number of unique characters in t
    formed = 0  # Number of unique characters in current window with desired frequency
    window_counts = {}
    
    # Initialize result tracking
    min_len = float('inf')
    min_left = 0
    min_right = 0
    
    # Two pointers for sliding window
    left = 0
    right = 0
    
    # Expand window with right pointer
    while right < len(s):
        # Add character from right to window
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # Check if frequency of current character matches requirement
        if char in t_freq and window_counts[char] == t_freq[char]:
            formed += 1
        
        # Try to contract window from left while valid
        while left <= right and formed == required:
            # Update minimum window if current is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left
                min_right = right
            
            # Remove character from left of window
            char = s[left]
            window_counts[char] -= 1
            
            # Check if window no longer satisfies requirement
            if char in t_freq and window_counts[char] < t_freq[char]:
                formed -= 1
            
            # Move left pointer forward
            left += 1
        
        # Move right pointer forward
        right += 1
    
    # Return result
    return "" if min_len == float('inf') else s[min_left:min_right + 1]

• Sliding window with two pointers: Use the expanding-contracting window pattern when you need to find a substring that satisfies certain conditions - expand the right pointer to meet the condition, then contract the left pointer to optimize it. This transforms a brute-force O(n²) approach into O(n).
• Frequency map comparison technique: Maintain two hash maps - one for the target character frequencies and one for the current window. Track a 'formed' counter that increments when a character reaches its required frequency, avoiding expensive full map comparisons on every iteration.
• Window validity optimization: Instead of checking all character counts repeatedly, use a single integer 'formed' variable that equals the number of unique characters in t that have been satisfied in the current window. The window is valid when formed == required_unique_chars.
• Premature window contraction pitfall: A common mistake is contracting the window (moving left pointer) before the window is valid. Always ensure your window first contains all required characters before attempting to minimize it, otherwise you'll miss valid solutions.
• Character frequency tracking pattern: When problems ask for 'contains all characters including duplicates', immediately think frequency maps + sliding window. This pattern extends to problems like finding anagrams, permutations in string, or any 'contains all elements' substring problem.
• Early termination optimization: Before starting the sliding window, check if len(s) < len(t) to return early. Also, filter s to only include characters present in t when s is much larger than t, reducing the search space significantly in sparse character scenarios.