HardLeetCode #76Sliding Window

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Constraints

m == s.length, n == t.length, 1 <= m, n <= 10^5

Examples

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Solution

Approach

Use sliding window with character frequency maps. Expand right to include all chars of t, then shrink left to minimize window while maintaining validity.

def minWindow(s, t):
    if not t or not s:
        return ""
    from collections import Counter
    dict_t = Counter(t)
    required = len(dict_t)
    left, right = 0, 0
    formed = 0
    window_counts = {}
    ans = float("inf"), None, None
    while right < len(s):
        c = s[right]
        window_counts[c] = window_counts.get(c, 0) + 1
        if c in dict_t and window_counts[c] == dict_t[c]:
            formed += 1
        while left <= right and formed == required:
            c = s[left]
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            window_counts[c] -= 1
            if c in dict_t and window_counts[c] < dict_t[c]:
                formed -= 1
            left += 1
        right += 1
    return "" if ans[0] == float("inf") else s[ans[1]:ans[2]+1]

Complexity

Time:O(m + n)

Space:O(m + n)

Hints

1.Use two hash maps for needed and current window counts
2.Track how many unique chars are satisfied
3.Shrink window when all chars satisfied

Asked at

Google