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 O(1) Validity Tracking

Expand the window until it contains all characters from t, then contract from the left to minimize. The key optimization: instead of re-checking all character counts each time, track how many unique characters currently meet their required frequency. When that count equals the number of unique characters in t, the window is valid.

Implementation

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_counts = Counter(t)
        need = len(t_counts)
        have = 0

        state = {}
        start = 0
        best_len = float('inf')
        best_l, best_r = 0, 0

        for end, char in enumerate(s):
            state[char] = state.get(char, 0) + 1
            if char in t_counts and state[char] == t_counts[char]:
                have += 1

            while have == need:
                if end - start + 1 < best_len:
                    best_len = end - start + 1
                    best_l, best_r = start, end + 1

                left_char = s[start]
                state[left_char] -= 1
                if left_char in t_counts and state[left_char] < t_counts[left_char]:
                    have -= 1
                if state[left_char] == 0:
                    del state[left_char]
                start += 1

        return s[best_l:best_r] if best_len != float('inf') else ""

The have counter updates in O(1): increment when a character’s count exactly meets its requirement, decrement when it drops below. This avoids re-scanning the frequency map on every window shift.

Complexity Analysis

Time Complexity: O(m + n), where m is the length of s and n is the length of t. Each character in s is added and removed at most once. The have == need check is O(1).
Space Complexity: O(1), since both dictionaries store at most 52 entries (uppercase + lowercase English letters).

Key Insights

O(1) Validity Check: Tracking have vs need avoids comparing full frequency maps on every step. have increments when a character exactly meets its required count, and decrements when it drops below.
Expand then Contract: Expand right to find a valid window, then greedily contract left while staying valid. Each character is visited at most twice, keeping the total work linear.
Only Relevant Characters Affect Validity: Characters not in t enter and leave the window without affecting have, so they don’t trigger unnecessary contraction.