参考：https://labuladong.github.io/algo/2/20/27/

滑窗思路

1. 使用双指针，left = right = 0，把 [left, right) 称为窗口。最开始[0, 0)是没有元素的
2. 先不断增加right，直到窗口内数据达到某条件
3. 此时转而增加left，以缩小窗口，直到窗口内数据不再符合某条件
4. 重复直到right到达结尾
   第2步相当于寻找可行解，第3步是优化可行解，最后找到最优。

【困难】76.最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：

【中等】567. 字符串的排列

https://leetcode.cn/problems/permutation-in-string/
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
提示：s1 和 s2 仅包含小写字母

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:left = 0right = 0valid = 0 # 记录符合条件的字符数目need = dict()for c in s1: # 初始化need字典if c in need: need[c] += 1else: need[c] = 1window = dict() # window计算的是滑窗里字符的个数while right < len(s2):c = s2[right] right += 1 # 加入一个元素if c in need:# 更新window字典if c in window: window[c] += 1else: window[c] = 1# 判断当前的字符是否符合要求if window[c] == need[c]:valid += 1# 判断是否需要收缩while right - left >= len(s1):# 此时所有字符都有且数量对if valid == len(need): return True# 缩小窗口d = s2[left]left += 1# 此时左端一定在window中if d in need:if window[d] == need[d]:valid -= 1window[d] -= 1return False