Minimum Window Substring

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

"YXAZ" is the shortest substring that includes "X", "Y", and "Z" from string t.

Approach

Use a sliding window with character counts. Build a frequency map of t and track how many required characters are still missing. Expand the right pointer, decrementing counts and reducing the missing count when a requirement is met. When all requirements are satisfied, shrink from the left to find the smallest valid window.

Why It Works

The window maintains the invariant that missing == 0 if and only if the current substring contains all required characters (including duplicates). Expanding right ensures we eventually satisfy the requirement; shrinking left while keeping the window valid guarantees minimality for each right endpoint. The best of these minima is the global minimum window.

Complexity

• Time: O(n)
• Space: O(1) (bounded by alphabet size)

Reference Implementation (Python)

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

        need = Counter(t)
        missing = len(t)
        left = 0
        best_len = float('inf')
        best_start = 0

        for right, ch in enumerate(s):
            if need[ch] > 0:
                missing -= 1
            need[ch] -= 1

            while missing == 0:
                window_len = right - left + 1
                if window_len < best_len:
                    best_len = window_len
                    best_start = left
                left_char = s[left]
                need[left_char] += 1
                if need[left_char] > 0:
                    missing += 1
                left += 1

        if best_len == float('inf'):
            return ""
        return s[best_start:best_start + best_len]