[76][困难][滑动窗口] 最小覆盖子串

输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)

        t_map = Counter(t)
        t_set = set(t_map.keys())
        t_count = sum(t_map.values())

        c_map, c_count = dict(), 0
        max_len, res = float('inf'), ''
        left = right = 0
        while right < n:
            c = s[right]
            right += 1

            if c in t_set:
                last_count = c_map.get(c, 0)
                if last_count < t_map[c]:
                    c_count += 1
                c_map[c] = c_map.get(c, 0) + 1
                if c_count == t_count:
                    if right - left < max_len:
                        max_len = right - left
                        res = s[left: right]

            while c_count == t_count:
                if right - left < max_len:
                    max_len = right - left
                    res = s[left: right]

                c = s[left]
                left += 1

                if c in t_set:
                    last_count = c_map.get(c, 0)
                    if last_count <= t_map[c]:
                        c_count -= 1
                    c_map[c] = c_map[c] - 1
                    if c_count < t_count:
                        break
        return res