Minimum Window Substring is the crown jewel of sliding window problems. The difference between a junior solution and a staff engineer solution comes down to how window validation is tracked.

1. The Trap: Comparing Two Hash Maps

In naive implementations, developers maintain two hash maps: target_counts and window_counts. Whenever the window slides, they loop through the keys of target_counts to see if the window is valid. That turns an $O(N)$ algorithm into $O(N cdot |Sigma|)$ with heavy hash table overhead!

2. The Staff Engineer Pattern: Single Vector + Deficit Counter

We can optimize this down to bare metal with two simple tricks:

1. Fixed 128-integer Array: Standard ASCII fits inside 128 indices. An array of 128 integers takes 512 bytes, fitting completely inside an L1 data cache line.
2. A Single Deficit Counter (required): We set required = len(t). When expanding the window with pointer r, if counts[s[r]] > 0, that character was actively needed, so we decrement required--. When required == 0, the window is 100% valid! We don’t have to check any other variables!

Clean Python 3.12 Implementation

def min_window(s: str, t: str) -> str:
    """Finds minimum window substring in strict O(|s| + |t|) time and O(1) space."""
    if not s or not t or len(s) < len(t):
        return ""

    # Frequency map using fixed 128 ASCII array
    freq = [0] * 128
    for char in t:
        freq[ord(char)] += 1

    required = len(t)
    min_len = float('inf')
    start_idx = 0
    left = 0

    for right in range(len(s)):
        r_char = ord(s[right])
        
        # If this character was still needed by t
        if freq[r_char] > 0:
            required -= 1
            
        freq[r_char] -= 1

        # While window satisfies all characters in t -> contract left boundary
        while required == 0:
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                start_idx = left

            l_char = ord(s[left])
            freq[l_char] += 1
            
            # If removing this character breaks the required quota
            if freq[l_char] > 0:
                required += 1
                
            left += 1

    return "" if min_len == float('inf') else s[start_idx : start_idx + min_len]

Complexity Breakdown

• Time Complexity: O(|s| + |t|). The right pointer advances |s| times. The left pointer advances at most |s| times. Total pointer advances = 2|s|.
• Space Complexity: O(1) auxiliary space. Exactly 128 integers on the stack.