roadmap/two-pointers/Minimum Window Substring

Minimum Window Substring

HardFacebookAmazonGoogleMicrosoftBloomberg

Problem

Given strings s and t, return the minimum window substring of s that contains all characters of t. Return empty string if no such window exists.

Intuition — the key insight

Sliding window with two frequency maps. Expand right until window contains all chars of t. Then shrink left while still valid. Track the minimum valid window seen. The 'formed' counter tracks how many unique characters from t have their required frequency in the window.

Approach

Sliding window with formed counter

need = frequency map of t. window = frequency map of current window. formed = how many chars satisfy their required frequency. Expand right, increment formed when a char reaches its required count. Shrink left while formed == len(need), updating minimum window.

Complexity

Time

O(|s| + |t|)

Space

O(|s| + |t|)

Each character in s is added and removed at most once. Building t's frequency map is O(|t|).

Solution code

Python

def minWindow(self, s: str, t: str) -> str:
    if not t: return ""
    
    need   = Counter(t)
    window = defaultdict(int)
    formed = 0
    required = len(need)
    
    lo = 0
    best = (float('inf'), 0, 0)  # (length, lo, hi)
    
    for hi, char in enumerate(s):
        window[char] += 1
        if char in need and window[char] == need[char]:
            formed += 1
        
        while formed == required:
            if hi - lo + 1 < best[0]:
                best = (hi - lo + 1, lo, hi)
            
            left_char = s[lo]
            window[left_char] -= 1
            if left_char in need and window[left_char] < need[left_char]:
                formed -= 1
            lo += 1
    
    return s[best[1]:best[2]+1] if best[0] != float('inf') else ""

Edge cases to remember

⚠t longer than s: impossible, return ''

⚠t has duplicate chars: need map handles this

⚠No valid window: return empty string

Hints

What pattern do you think this problem uses?