Q26: Minimum Window Substring. - DSA Patterns (Multi-Lang)

In Simple Words: Count target characters in t. Expand r until all target characters are matched (have === need). Then contract l to minimize window length while still valid.

Time: $O(N + M)$ | Space: $O(\Sigma)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def minWindow(s: str, t: str) -> str:
    if not t or not s: return ""
    from collections import Counter
    target = Counter(t)
    window = {}
    have, need = 0, len(target)
    res, min_len = [-1, -1], float('inf')
    l = 0
    for r, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in target and window[c] == target[c]:
            have += 1
        while have == need:
            if (r - l + 1) < min_len:
                min_len = r - l + 1
                res = [l, r]
            window[s[l]] -= 1
            if s[l] in target and window[s[l]] < target[s[l]]:
                have -= 1
            l += 1
    return s[res[0]:res[1] + 1] if min_len != float('inf') else ""