26. 最小覆盖子串.md

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

#我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。
#我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        left = 0
        min_len = float('inf')
        res = ''
        #用一个哈希表动态维护窗口中所有的字符以及它们的个数
        target = {}
        cnt = 0
        for c in t:
            if c not in target:
                target[c] = 1
                cnt += 1
            else:
                target[c] += 1

        for ind, c in enumerate(s):
            if c in target:
                target[c] -= 1
                if target[c] == 0:
                    cnt -= 1
            while not cnt:
                cur_len = ind-left+1
                if cur_len < min_len:
                    min_len = cur_len
                    res = s[left:ind+1]
                if s[left] in target:
                    target[s[left]] += 1
                    if target[s[left]] > 0:
                        cnt += 1
                left += 1
        return res