Leetcode Link: 76. 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
解法一
思路：滑动窗口
用 left 和 right 表示滑动窗口的左边界和右边界，通过改变 left 和 right 来扩展和收缩滑动窗口。
在这里，通过维护一个”当前所需字母”的变量
need来维护窗口信息，而不是使用一个一对一的window变量来记录当前窗口内有什么字母及出现多少次（开始太死板，总想用一个 window 变量，记录当前窗口内有什么，有多少个）
步骤一
不断增加 right 使滑动窗口增大，直到窗口包含了 T 的所有元素
怎么判断窗口已经包含了 T 中所有需要的元素？
步骤二
不断增加 left 使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
怎么确定"碰到了一个必须包含的元素"，同时又保证这个元素在
need中不是重复的？比如，窗口中目前有两个所需要的字符
b，那么显然只吐出一个b的话还可以继续吐出其他的元素，可能同样保证窗口内有重复的子串
步骤三
让 left 再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到 right 超出了字符串 S 范围。
问题答案：
如何判断滑动窗口包含了 T 的所有元素？
我们用一个字典 need 来表示当前滑动窗口中需要的各元素的数量 (即用 need 来维护窗口信息，而不是一一对应的 window 变量)，一开始滑动窗口为空，用 T 中各元素来初始化这个 need，当滑动窗口扩展或者收缩的时候，去维护这个 need 字典，例如当滑动窗口包含某个元素，我们就让 need 中这个元素的数量减 1，代表所需元素减少了 1 个；当滑动窗口移除某个元素，就让 need 中这个元素的数量加 1。
记住一点：need 始终记录着当前滑动窗口下，我们还需要的元素数量，我们在改变 left 和 right 时，需同步维护 need。
值得注意的是，只要某个元素包含在滑动窗口中，我们就会在 need 中存储这个元素的数量，如果某个元素存储的是负数代表这个元素是多余的。比如当 need 等于{‘A’:-2,‘C’: 1}时，表示当前滑动窗口中，我们有 2 个 A 是多余的，同时还需要 1 个 C。这么做的目的就是为了步骤二中，排除不必要的元素，数量为负的就是不必要的元素，而数量为 0 表示刚刚好。
回到问题中来，那么如何判断滑动窗口包含了 T 的所有元素？结论就是当 need 中所有元素的数量都小于等于 0 时，表示当前滑动窗口不再需要任何元素。
进一步优化
如果每次判断滑动窗口是否包含了 T 的所有元素，都去遍历 need 看是否所有元素数量都小于等于 0，这个会耗费 O (k) O (k) 的时间复杂度，k 代表字典长度，最坏情况下，k 可能等于 len (S)。 其实这个是可以避免的，我们可以维护一个额外的变量 needCnt 来记录所需元素的总数量，当我们碰到一个所需元素 c，不仅 need[c]的数量减少 1，同时 needCnt 也要减少 1，这样我们通过 needCnt 就可以知道是否满足条件，而无需遍历字典了。
need记录了遍历到的所有元素，而只有need[c]>0时，代表c就是所需元素，即need[c]>0时才有效。
题解：
class Solution:
def minWindow(self, s: str, t: str) -> str:
# 特殊情况，target 比 s 要长，肯定没有
if len(t) > len(s):
return ""
# 这里维护的窗口内的信息，不是窗口里有什么，而是维护的窗口里目前缺什么（多什么）
need = collections.defaultdict(int)
need_cnt = 0
for c in t:
need_cnt += 1
need[c] += 1
res = [0, float('inf')] # 结果的左右区间
left = 0 # 左指针
for right, c in enumerate(s):
# 如果是“需要元素”，则 cnt - 1
# 注意，> 0 的才是“需要元素”
if need[c] > 0:
need_cnt -= 1
# 维护窗口内的信息
need[c] -= 1
# 判断是否需要收缩
if need_cnt == 0: # ==0 表示现在什么元素也不需要了，即需要的元素都在窗口里了
while(1):
if need[s[left]] == 0:
# 再收缩就该缺东西了，所以到此收缩完毕
break
else:
need[s[left]] += 1 # 收缩后修改need
left += 1
# 结果更新，要小区间
# 窗口是左闭右闭的
if right+1-left < res[1]-res[0]:
res =[left, right+1]
# left 再走一步，吐出一个必需的，就可以开始新的一轮了
need[s[left]] += 1 # 别忘了维护窗口信息，我就忘了
left += 1
need_cnt += 1
# 如果就没有覆盖的子串，那么需要处理一下
if res[1]-res[0] == float('inf'):
return ""
else:
return (s[res[0]:res[1]])在复习时提出了相同思路的不同写法
class Solution:
def minWindow(self, s: str, t: str) -> str:
res = [0] *(len(s) + 1) #随便弄的，就是为了能把res更新
left = 0
right = 0
need = collections.defaultdict(int)
need_cnt = 0
for c in t:
need[c] += 1
need_cnt += 1
while(right < len(s)):
if need[s[right]] > 0:
need_cnt -= 1
need[s[right]] -= 1
# 出窗
while(left <= right and need[s[left]] < 0): # 必需<0，0或者>0都是我们需要的，不能丢掉
need[s[left]] += 1
left += 1
if need_cnt == 0 and (right-left+1)<len(res):
res = s[left:right+1]
right += 1
return "" if len(res) == (len(s) + 1) else res
解法二
思路：暴力搜索法，两个 for 可以完成。略
启发和联系
不要死板的认为滑动窗口时维护窗口信息的方式只能是通过新建一个 window 变量来和窗口内的内容一一对应，而是要灵活的记录窗口信息，本题中就采用了 need 变量，用来指示窗口内还”缺少”什么来维护的窗口信息。
collections.defaultdict(type) 的用法，参考该博客
概括来说，本质上和 dict() 一样都是字典，区别在于使用 collections.defaultdict(type) 创建的字典，在遇到不存在的 key 时，直接使用不会报错，而是会使用默认值，若 type 为 int，则默认值为 0