Minimum Window Substring

Problem

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

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Solution

Approach: Sliding Window with Two Pointers

The key insight is to use a sliding window that expands to find a valid window (containing all characters from t), then contracts to minimize the window size while keeping it valid.

We maintain:

t_count: frequency map of characters we need
window_count: frequency map of characters in current window
have: number of unique characters in window with desired frequency
need: number of unique characters required from t

Algorithm:

Expand window with right pointer until we have all required characters
Contract window with left pointer while keeping it valid
Track the minimum valid window

Implementation

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        # Count characters in t
        t_count = {}
        for char in t:
            t_count[char] = t_count.get(char, 0) + 1

        # Number of unique characters in t that need to be in the window
        need = len(t_count)
        have = 0

        # Window character counts
        window_count = {}

        # Result: (window_length, left, right)
        result = [-1, 0, 0]
        min_length = float('inf')

        left = 0
        for right in range(len(s)):
            # Add character from right to window
            char = s[right]
            window_count[char] = window_count.get(char, 0) + 1

            # Check if this character's frequency matches what we need
            if char in t_count and window_count[char] == t_count[char]:
                have += 1

            # Contract window while we have all required characters
            while have == need:
                # Update result if this window is smaller
                if (right - left + 1) < min_length:
                    min_length = right - left + 1
                    result = [min_length, left, right]

                # Remove character from left
                left_char = s[left]
                window_count[left_char] -= 1
                if left_char in t_count and window_count[left_char] < t_count[left_char]:
                    have -= 1

                left += 1

        # Return substring or empty string
        length, l, r = result
        return s[l:r + 1] if length != -1 else ""

Complexity Analysis

Time Complexity: O(m + n), where m is the length of s and n is the length of t. We process each character in s at most twice (once by right pointer, once by left pointer), and we iterate through t once to build the frequency map.
Space Complexity: O(m + n), for storing the character frequency maps. In practice, if we’re limited to English letters, this is O(1).

Key Insights

Two-Phase Window: We expand the window until it’s valid (contains all characters from t), then contract it while maintaining validity. This ensures we find the minimum window.
Frequency Matching: We track both the counts and the number of unique characters with matching frequencies (have vs need). When have == need, our window contains all required characters with correct frequencies.
Greedy Contraction: Once we have a valid window, we greedily contract from the left to minimize the window size. We stop contracting when the window becomes invalid.
Character Relevance: We only care about characters that appear in t. Other characters in s don’t affect our have counter but are included in the window size.