最小覆盖子串
Minimum Window Substring
本机进度仅保存在当前浏览器
题目描述
给你字符串 s 和 t，返回 s 中涵盖 t 所有字符（含重复次数）的最小子串；不存在则返回空串。数据保证答案唯一。
示例：s = "ADOBECODEBANC"，t = "ABC"，输出 "BANC"。
解题思路
- 不定长窗口模板题：右指针扩张到窗口满足要求，再尽量收缩左指针，反复记录最短可行窗口。
- 用两个计数器：need 记录 t 的字符需求，window 记录当前窗口内相关字符数。
- 引入满足变量 formed：每当某字符数量首次达标 formed 加一，收缩时首次跌破则减一，避免每次全表比较。
- 收缩到刚好不满足为止，期间的最小窗口即答案，整体 O(|s| + |t|)。
参考实现
查看参考实现Python · 建议先自行作答
from collections import Counter
def minWindow(s, t):
need = Counter(t)
window = {}
formed = l = 0
best_len, best_l = len(s) + 1, 0
for r, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if ch in need and window[ch] == need[ch]:
formed += 1
# 满足全部需求时收缩左端
while formed == len(need):
if r - l + 1 < best_len:
best_len, best_l = r - l + 1, l
left = s[l]
window[left] -= 1
if left in need and window[left] < need[left]:
formed -= 1
l += 1
return '' if best_len > len(s) else s[best_l:best_l + best_len]