76. 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

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

提示：

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring

思路及分析

这道题使用『滑动窗口』，而难点在于 如何知道滑动窗口已经包含了T中所有字符

使用字典记录T的所有字符出现的次数，并可设置一个T中字符的总数needCnt

在遍历S时，只要遇见了是T中的字符并且在hashmap的次数大于0，则needCnt减1

当needCnt = 1时，即说明当前滑动窗口包含了T中的所有字符

为了使这个滑动窗口尽可能小，所以在保证滑动窗口包含T中所有字符的情况下收缩左边界

完整代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        left: str = 0
        length: int = len(s)
        need = defaultdict(int)
        # 构建hashmap
        for i in t:
            need[i] += 1
        # T字符总数
        needCnt: int = len(t)
        res: list = [0, float('inf')]
        for right in range(length):
            # 大于0表示当前字符是T中的字符
            if need[s[right]] > 0:
                needCnt -= 1
            # 如果s[right]不存在T，则会被减成负数
            # 如果s[right]存在T中，则可能会减到0
            need[s[right]] -= 1
            
            # 说明t的字符已被滑动窗口全部包含
            if needCnt == 0:
                while need[s[left]] != 0:
                    # 如果左边界元素是t中的元素，则退出循环
                    # 一直收缩左边界，最终使得滑动窗口刚刚包含t内的字符
                    need[s[left]] += 1
                    left += 1
                # 保存更小的结果
                if right - left < res[1] - res[0]:
                    res = [left, right]
                need[s[left]] += 1
                left += 1
                needCnt += 1
                
        return '' if res[1] > length else s[res[0]:res[1]+1]