LeetCode 76 - Minimum Window Substring

Given two strings s and t, this Hard string problem asks for the shortest contiguous substring in s containing every character of t (including duplicate frequencies). I solved this in O(S + T) time using a variable-size sliding window with two frequency hash maps and a have/need condition tracker.

---

Problem link and explanation

• Problem: 76. Minimum Window Substring
• Summary: Return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return the empty string "".

Comparing the entire character frequency map on every pointer shift adds an unnecessary factor to the time complexity. By defining need as the number of unique characters required and have as the number of unique characters currently satisfied, window validity is evaluated in O(1) time.

---

Approach

Build target_counts for t, and dynamically maintain window_counts as the sliding window expands and contracts.

target_counts = {}
for char in t:
    target_counts[char] = target_counts.get(char, 0) + 1

window_counts = {}
have = 0
need = len(target_counts)

res = [-1, -1]
res_len = float("inf")
left = 0

for right in range(len(s)):
    char = s[right]
    window_counts[char] = window_counts.get(char, 0) + 1

    if char in target_counts and window_counts[char] == target_counts[char]:
        have += 1

    while have == need:
        if (right - left + 1) < res_len:
            res = [left, right]
            res_len = right - left + 1

        left_char = s[left]
        window_counts[left_char] -= 1

        if (
            left_char in target_counts
            and window_counts[left_char] < target_counts[left_char]
        ):
            have -= 1

        left += 1

1. Expand window: Advance right and increment window_counts[char]. When the count of char matches target_counts[char], increment have.
2. Contract window: While have == need, record the minimal window indices, then advance left to shrink the window from the left.
3. Invalidate condition: If removing left_char causes its count to fall strictly below target_counts[left_char], decrement have, exiting the inner loop.

---

Complexity analysis

• Time complexity: O(S + T)
  • Counting t takes O(T) time. Both left and right traverse s at most once in a single direction, giving O(S) traversal.
• Space complexity: O(S + T)
  • Hash tables store character frequencies proportional to the alphabet size of s and t.

---

Implementation code

class Solution:

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

        target_counts = {}
        for char in t:
            target_counts[char] = target_counts.get(char, 0) + 1

        window_counts = {}

        have = 0
        need = len(target_counts)

        res = [-1, -1]
        res_len = float("inf")
        left = 0

        for right in range(len(s)):
            char = s[right]
            window_counts[char] = window_counts.get(char, 0) + 1

            if char in target_counts and window_counts[char] == target_counts[char]:
                have += 1

            while have == need:
                if (right - left + 1) < res_len:
                    res = [left, right]
                    res_len = right - left + 1

                left_char = s[left]
                window_counts[left_char] -= 1

                if (
                    left_char in target_counts
                    and window_counts[left_char] < target_counts[left_char]
                ):
                    have -= 1

                left += 1

        l, r = res
        return s[l : r + 1] if res_len != float("inf") else ""

---

Summary and reflection

Tracking window validity via the scalar comparison have == need avoids scanning dictionary keys on each iteration. Incrementing and decrementing have precisely when a character hits its exact target frequency keeps the sliding window logic linear and optimal.