from collections import Counter

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

    need = Counter(t)       # chars we need
    have = {}               # chars we have in window
    formed = 0              # how many unique chars are satisfied
    required = len(need)    # how many unique chars we need

    left = 0
    min_len = float('inf')
    min_left = 0

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

        # check if this char's count satisfies the requirement
        if char in need and have[char] == need[char]:
            formed += 1

        # try to shrink window from left while it's valid
        while formed == required:
            # update minimum
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left

            # remove leftmost char
            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1

    return s[min_left:min_left + min_len] if min_len != float('inf') else ""

# Time: O(|s| + |t|), Space: O(|s| + |t|)
# s="ADOBECODEBANC", t="ABC" -> "BANC"
Sliding Window Pattern

Sliding Window Pattern

Sliding Window Pattern
