Minimum Window Substring
给定两个字符串 s 和 t。找出 s 中包含 t 的所有字符的最短子字符串，重复字符也要计入：如果 t 中某个字母出现两次，子字符串中至少也要出现两次。字符顺序不限，也可以包含其他字符。
如果有多个长度最短的子字符串，返回最靠左的那个。如果没有子字符串包含 t 中的所有字符，则返回空字符串。
函数
- sstring
- 要搜索的字符串
- tstring
- 窗口必须包含的字符，允许重复
- 返回值string
- 包含 t 中所有内容的 s 的最短子字符串；如果有多个，则取最靠左的那个；如果不存在，则返回空字符串
约束条件
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104s和t只包含英文字母。大写字母和小写字母是不同的字符。- 如果有多个最短子字符串，答案是最靠左的那个；如果不存在这样的子字符串，答案就是
""。
示例
- 输入
- s = "mappingtheplan"t = "nap"
- 输出
- "plan"
- 解释
- 从左边开始第一个包含
n、a和p的窗口是appin，共五个字符。plan用四个字符包含了这三个字母，而没有任何连续的三个字符能做到这一点。
- 输入
- s = "banana"t = "aan"
- 输出
- "ana"
- 解释
t需要两个a和一个n。索引 1 处的ana正好包含这些字符。第二个ana从索引 3 开始，因此会选择最靠左的那个。
- 输入
- s = "Coddy"t = "cd"
- 输出
- ""
- 解释
C在Coddy中是大写字母，与c是不同的字符。没有任何子字符串包含小写字母c，所以答案是空字符串。
进阶
当 t 很短而 s 很长时，s 中的大部分内容都无关紧要。你能让窗口只在包含 t 中某个字母的位置之间跳转吗？
提示
逐个打开提示，每个都会多透露一点。
一个包含
t全部内容的窗口变长后仍然包含全部内容，而一个有所遗漏的窗口变短后仍然会有所遗漏。利用这一点，避免尝试每一种起点和终点的组合。将右边界向前移动，直到窗口覆盖
t。然后，只要窗口仍覆盖t，就向前移动左边界，并在每次移动时记录它。两个边界都不需要向后移动。记录一个表，统计窗口还需要每个字符的多少个副本，并用一个数字
missing表示总共还缺多少个副本。一个字符进入窗口时，只有在它仍然是需要的字符时，才会让missing减少；一个字符离开窗口时，只有在窗口中该字符的数量不足时，才会让missing增加。只有当missing为 0 时，窗口才恰好包含t。
题解
窗口中各字符的数量才重要，顺序并不重要。向右移动右边界，直到窗口包含 t，然后在窗口仍包含 t 时移动左边界。两个边界都不会后退。用一个缺失字符计数器，就能一步判断窗口是否包含 t。
从每个起点扩展一个窗口
结果正确，但无法在最大的测试中运行完毕
思路
固定一个起点，每次向右扩展一个字符，并记录每个字符出现的次数。每扩展一步，就检查 t 使用的每种 u 字母。第一个满足条件的终点会给出从这个起点开始的最短覆盖窗口，因此找到后就停止。起点从左向右移动，只有窗口严格变短时才更新最佳结果，因此长度相同时会保留最靠左的窗口。
如果不存在这样的窗口，每个起点都要一直读取到 s 的末尾：大约需要 n²/2 步，当 n = 5 × 10^4 时为 1.25 × 10^9 步。
算法
- 统计
t所需的每个字母的数量。 - 对于每个
start，清空计数表，然后向右移动end，并添加s[end]。 - 当窗口中每个字母的数量都足够时，如果它严格短于当前最佳窗口，就保留它，然后转到下一个
start。 - 返回最佳窗口；如果没有窗口覆盖
t，则返回""。
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
best_start, best_len = 0, len(s) + 1
for start in range(len(s)):
have = [0] * 128 # counts inside s[start..end]
for end in range(start, len(s)):
have[ord(s[end])] += 1
if all(have[c] >= need[c] for c in letters):
# The first end that covers t gives the shortest window from this start.
if end - start + 1 < best_len:
best_start, best_len = start, end - start + 1
break
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]检查每个字母的滑动窗口
思路
向覆盖窗口添加字符后，窗口仍然覆盖目标；从缺少字符的窗口中移除字符后，窗口仍然缺少字符。因此，随着起点向右移动，最短覆盖窗口的终点绝不会向左移动。
不会漏掉任何窗口。取最佳窗口，从 L 到 R。如果在 right 到达 R 之前，left 就越过了 L，那么从 L 开始的更短窗口就必须覆盖 t。因此，当 right 到达 R 时，收缩过程会让 left 移动到 L，并记录该窗口。
每个边界最多移动 n 次，但每次检查都会读取最多 u 个计数：O(n·u)。
算法
- 统计
t中每个字符需要的数量；将left = 0，并将最佳长度设为n+1。 - 对于每个
right，将s[right]加入窗口的计数中。 - 当
t中每个字符的数量都足够时，如果窗口严格更短，就记录该窗口，然后移除s[left]，并将left向前移动。 - 返回最佳窗口；如果最佳长度仍为
n+1，则返回""。
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
have = [0] * 128 # counts inside s[left..right]
def covers():
for c in letters:
if have[c] < need[c]:
return False
return True
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
have[ord(s[right])] += 1 # expand on the right
while covers(): # shrink from the left while the window still covers t
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
have[ord(s[left])] -= 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]使用缺失计数器的滑动窗口
思路
用一个数字替代扫描。设 need[c] 表示 t 中需要的 c 的数量减去窗口中的数量；负值表示有多余字符。设 missing 表示窗口还缺少的字符数量，初始值为 t 的长度。当 missing 为 0 时，窗口恰好覆盖 t。
当某个字符进入窗口时，如果它的 need 大于 0，就能填补一个缺口，因此 missing 会减少。移除某个字符后，如果它的 need 增至大于 0，就会产生一个缺口，因此 missing 会增加。多余字符不会影响它。对于 banana 和 t = aan，missing 首次变为 0 时，窗口是 bana；移除多余的 b 后，ana 仍然覆盖了 t。
每个字符只进入和离开一次，每次操作的开销固定：时间复杂度为 O(n + m)，使用一个包含 128 个计数值的表。
算法
- 将
need填入t中各字符的计数；将missing设为t的长度，将left = 0，并将最佳长度设为n+1。 - 遍历每个
right：如果need[s[right]]大于 0，就减少missing；然后减少need[s[right]]。 - 当
missing为 0 时，如果当前窗口严格更短，就记录该窗口。增加need[s[left]]；如果它现在大于 0，就增加missing。将left向前移动。 - 返回最佳窗口；如果最佳长度仍为
n+1，则返回""。
def minWindow(s, t):
# need[c]: copies of c that t asks for minus copies inside the window.
# Positive means the window still lacks c; negative means it holds spares.
need = [0] * 128
for ch in t:
need[ord(ch)] += 1
missing = len(t) # characters of t the window does not cover yet
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
c = ord(s[right])
if need[c] > 0: # this copy fills a gap
missing -= 1
need[c] -= 1
while missing == 0: # the window covers t: record it, then shrink
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
c = ord(s[left])
need[c] += 1
if need[c] > 0: # gave away a copy t needs
missing += 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]
易错点和边界情况
- 统计字母种类，而不是出现次数。
t = aan需要两个a，所以ban无法满足要求。 - 每当字符进入或离开窗口时，都修改
missing。这样，多余的a也会被计入，窗口缺少n时，missing也可能变成 0。 - 遇到长度相同的窗口时替换最佳窗口。在第二个示例中，这会返回索引为 3 的
ana。 - 用
n表示“未找到”的长度。如果答案是整个s，它的长度也是n；应从n+1开始。 - 创建一个包含 26 个槽位、通过
c - 'a'索引的表。大写字母（如第三个示例中的字母）会超出这个范围。
常见问题3
最小覆盖子串的时间复杂度是多少？
缺失计数窗口的运行时间为 O(n + m)，其中 n 和 m 分别是 s 和 t 的长度。构建表时会读取一次 t，而 s 中的每个字符最多进入和离开窗口各一次。额外的内存用于为每个字符编码保存一个计数。
为什么左边缘不会向后移动？
只有当从该位置开始的窗口覆盖了 t 后，左边界才会越过该位置，而且这个窗口是从该位置开始、能够覆盖 t 的最短窗口。从那里开始、结束位置更靠后的任何窗口都更长，因此回头查找不可能找到更好的答案。
最小覆盖子串与在字符串中查找字母异位词有什么不同？
字母重排词恰好包含 t 中的所有字母，因此它的窗口长度固定为 m，每次向前滑动一格。这里允许有额外字符，因此长度也是答案的一部分：窗口逐渐扩大，直到覆盖 t；只要仍然覆盖 t，窗口就会缩小。
def minWindow(s, t):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "mappingtheplan" t = "nap"
预期输出
"plan"