76. 最小覆盖子串（难）

• 题目
• 滑动窗口

题目

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

• 注意：

  对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

滑动窗口

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = {}    # 存储字符串 t 中各个字符的需求量
        window = {}  # 存储滑动窗口中各个字符的出现次数
        for c in t:#遍历字符串t
            need.setdefault(c, 0)#访问不存在的键时自动创建并将值设置为 0
            need[c] += 1  # 统计字符串 t 中各个字符的需求量

        left = 0    # 滑动窗口的左指针
        right = 0   # 滑动窗口的右指针
        valid = 0   # 记录满足需求的字符数
        start = 0   # 最小覆盖子串的起始位置
        length = float('inf')   # 最小覆盖子串的长度

        while right < len(s):
            c = s[right]    # 当前字符
            right += 1      # 右指针右移

            if c in need:#当前字符是目标字符中的
                window.setdefault(c, 0)#访问不存在的键时自动创建并将值设置为 0
                window[c] += 1  # 更新滑动窗口中当前字符的出现次数
                if window[c] == need[c]:
                    valid += 1  # 如果滑动窗口中当前字符的出现次数达到需求量，增加满足需求的字符数

            while valid == len(need):#每个字符的次数都达到了要求
                if right - left < length:#当前窗口的长度是否小于已记录的最小覆盖子串长度 length。
                    start = left#如果是，则更新最小覆盖子串的起始位置和长度
                    length = right - left  # 更新最小覆盖子串的起始位置和长度

                d = s[left]   # 将要移出窗口的字符
                left += 1     # 左指针右移

                if d in need:#当前字符是目标字符中的
                    if window[d] == need[d]:#如果滑动窗口中当前字符等于目标字符的值
                        valid -= 1   # 如果移出窗口的字符导致窗口不再满足需求，则减少满足需求的字符数
                    window[d] -= 1  # 更新滑动窗口中移出字符的出现次数

        return "" if length == float('inf') else s[start:start + length]  # 返回最小覆盖子串