LeetCode Solutions Blog

Minimum Window Substring

Number: 76

Difficulty: Hard

Paid? No

Problem Description

Given two strings s and t, find the minimum window in s which contains all the characters (including duplicates) from t. If no such window exists, return the empty string.

Key Insights

Use a sliding window approach to dynamically adjust the window boundaries.
Utilize a hash table (or dictionary) to keep track of the frequency of characters required (from t) and the frequency within the current window.
Expand the window until it satisfies the requirements, then contract to minimize the window.
Efficiently update counts and check valid window with two pointers (left and right).

Space and Time Complexity

Time Complexity: O(m + n), where m is the length of s and n is the length of t. Space Complexity: O(m + n) in the worst case due to the storage for the hash maps.

Solution

We use a sliding window technique with two pointers representing the window's boundaries. First, create a frequency map of characters from t. Then, expand the right pointer to include characters in the window until the window contains all required characters (meeting or exceeding the counts in t). Once the requirement is met, try contracting the window by moving the left pointer to reduce its size while still maintaining a valid window. Throughout the process, if a valid window is found that is smaller than the previously recorded minimum window, update the minimum. The solution leans heavily on hash tables to track counts and compares them against the required counts from t.

Code Solutions

# Python implementation of Minimum Window Substring solution

def minWindow(s: str, t: str) -> str:
    # If t is longer than s, no solution exists.
    if len(t) > len(s):
        return ""
    
    # Dictionary to store the frequency of each character in t.
    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1

    # Dictionary to keep track of the characters in the current window.
    window_freq = {}
    
    required = len(t_freq)  # Unique characters in t to be matched
    formed = 0  # Number of unique characters in the current window that meet required frequency
    
    # (window_length, left, right)
    answer = (float('inf'), None, None)
    
    l = 0  # Left pointer
    # Start sliding the window with the right pointer.
    for r, char in enumerate(s):
        # Add the current character to the window counter.
        window_freq[char] = window_freq.get(char, 0) + 1
        
        # Check if the current character's frequency in the window matches that in t.
        if char in t_freq and window_freq[char] == t_freq[char]:
            formed += 1
        
        # Try and contract the window if all characters are matched.
        while l <= r and formed == required:
            character = s[l]
            
            # Update answer if the current window is smaller than the previous best.
            if r - l + 1 < answer[0]:
                answer = (r - l + 1, l, r)
            
            # The character at the left is going to be removed from the window.
            window_freq[character] -= 1
            if character in t_freq and window_freq[character] < t_freq[character]:
                formed -= 1
            
            # Move the left pointer ahead.
            l += 1

    # Return the smallest window, if found.
    return "" if answer[0] == float('inf') else s[answer[1]:answer[2]+1]

# Example usage:
if __name__ == "__main__":
    s = "ADOBECODEBANC"
    t = "ABC"
    print(minWindow(s, t))  # Expected output: "BANC"