Minimum Window Substring

Given strings s and t, return the minimum-length contiguous substring of s that contains every character of t — including duplicates — or an empty string if none exists. The machine must find the tightest window in one pass.

The key insight: this is a two-pointer sliding window with a satisfied counter. The window [left, right) grows right until it contains all of t's characters; then it shrinks from the left while the window is still satisfied, tracking the minimum. The trick is counting satisfaction — how many distinct characters currently have enough occurrences — instead of re-scanning on every move.

Approach:

1. Count t into a need map; track how many character types are unmet.
2. Extend right; when a character's count reaches its need, decrement unmet.
3. While unmet == 0, record the window, then advance left — if a character falls below its need, it becomes unmet again.

def min_window(s, t):
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    unmet = len(need)
    have = {}
    left = best_left = 0
    best_len = float("inf")
    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            unmet -= 1
        while unmet == 0:
            if right - left + 1 < best_len:
                best_len, best_left = right - left + 1, left
            have[s[left]] -= 1
            if s[left] in need and have[s[left]] < need[s[left]]:
                unmet += 1
            left += 1
    return "" if best_len == float("inf") else s[best_left:best_left + best_len]

Time: O(n + m). Space: O(m).

Trickiest edge case: t with duplicates — "aa" needs two as, so the satisfaction check compares counts, not presence, or the window "a" would be wrongly accepted.