最小窗口子串

def min_window_opt(s, t):
    if t == "": return ""
    countT, window = {}, {}
    for c in t: countT[c] = 1 + countT.get(c, 0)
    have, need = 0, len(countT)
    res, resLen = [-1, -1], float("infinity")
    l = 0
    for r in range(len(s)):
        c = s[r]
        window[c] = 1 + window.get(c, 0)
        if c in countT and window[c] == countT[c]:
            have += 1
        while have == need:
            if (r - l + 1) < resLen:
                resLen = r - l + 1
                res = [l, r]
            window[s[l]] -= 1
            if s[l] in countT and window[s[l]] < countT[s[l]]:
                have -= 1
            l += 1
    l, r = res
    return s[l : r + 1] if resLen != float("infinity") else ""

def min_window_brute(s, t):
    if not t: return ""
    def contains_all(counts_s, counts_t):
        for char in counts_t:
            if counts_s.get(char, 0) < counts_t[char]:
                return False
        return True
    
    t_counts = {}
    for c in t: t_counts[c] = 1 + t_counts.get(c, 0)
    
    res, res_len = "", float("inf")
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i : j + 1]
            sub_counts = {}
            for c in sub: sub_counts[c] = 1 + sub_counts.get(c, 0)
            if contains_all(sub_counts, t_counts):
                if (j - i + 1) < res_len:
                    res_len = j - i + 1
                    res = sub
    return res