链接：最小覆盖子串
给定两个字符串S和T，在S中找到包含T中每个字符的最新连续子串，子串中每个字符出现的次数大于等于在T中出现的次数。
解法：滑动窗口
给定两个下表left、right定义一个窗口，通过移动窗口的左右边界来求解问题。
- left、right分别初始化为0、0
- 先向右移动right扩大窗口，直到包含T中所有字符及频数。
- 再向右移动left来缩小窗口，直到不能包含T中所有字符及频数。
- 这时，记录刚好包含T中字符及频数的left、right值并计算子串长度。
重复上述过程，记录多个覆盖子串，并记录最小子串。
class Solution:
def minWindow(self, s: str, t: str) -> str:
# 判断当前窗口内的字符及频数是否覆盖字符串T
def is_covered(winfreq, tfreq):
for c in tfreq:
if tfreq[c] > winfreq.get(c, 0):
return False
else:
return True
tfreq = dict()
for e in t:
tfreq[e] = tfreq.get(e, 0) + 1
winfreq = dict()
minLen = len(s)+1
left, right = 0, 0
begin, end = 0, 0
while left < len(s) and right < len(s):
# 窗口右边界不停移动直到覆盖字符串T
while right < len(s) and not is_covered(winfreq, tfreq):
winfreq[s[right]] = winfreq.get(s[right], 0) + 1
right += 1
# 窗口左边界不停移动直到不能覆盖字符串T
while left < len(s) and is_covered(winfreq, tfreq):
winfreq[s[left]] -= 1
left += 1
# 更最小覆盖子串的信息
if minLen > right-left+1:
begin = left -1
end = right
minLen = right-left+1
if minLen == len(s) + 1:
return ""
else:
return s[begin:end]
