题目描述
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
输入
字符串 s 和 t
输出
s 中涵盖 t 所有字符的最小子串；若不存在则返回 ""
约束条件
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成（大小写均可）
进阶约束
你能设计一个在 时间内解决此问题的算法吗？
示例1
输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例2
输入：s = "a", t = "a"输出："a"解释：整个字符串 s 就是最小覆盖子串。
示例3
输入：s = "a", t = "aa"输出：""解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
解题思路
题目要求在 s 中找一个最短的连续子串，使得该子串包含 t 中的所有字符，且每个字符的出现次数不少于 t 中的次数。这与之前做过的「找到字符串中所有字母异位词」有相似之处——都是在滑动窗口中维护字符频次。但这里 t 的字符可以在子串中分散出现（中间夹着无关字符），且窗口长度不固定，我们需要找到最短的合法窗口。
核心思路：右指针 i 不断扩展窗口，每当窗口内的字符频次满足 t 的要求时，尝试从左边收缩窗口以找到当前右边界下的最短合法窗口，同时更新全局最优解。
从暴力枚举出发
最朴素的做法：枚举 s 的所有子串（ 个），对每个子串检查是否包含 t 的所有字符（），总体 。对于 的数据规模，这显然不可行。
稍作优化：枚举起点 i 后，向右扩展终点，同时维护窗口内各字符的计数。当计数满足 t 的要求时，记录当前子串长度，然后尝试下一个起点。这样减少到 ，但仍然不够快：
from collections import Counter
class Solution: def minWindow(self, s: str, t: str) -> str: ct = Counter(t) res = '' for i in range(len(s)): cs = Counter() for j in range(i, len(s)): cs[s[j]] += 1 # 检查当前窗口是否覆盖 t ok = True for ch in ct: if cs[ch] < ct[ch]: ok = False break if ok and (res == '' or j - i + 1 < len(res)): res = s[i:j + 1] return res瓶颈：每个起点都重新建一个 Counter 并从零开始累加，相邻起点之间的窗口信息完全没有复用。能否让左右边界各自只向前移动，不重复计算？
滑动窗口：cnt 计数 + 超频左缩
回顾「无重复字符的最长子串」和「找到字符串中所有字母异位词」中的滑动窗口套路：右指针扩展、左指针在条件不合法时收缩。本题可以延续这一思路，关键在于如何高效判断「当前窗口是否覆盖了 t」。
维护以下状态：
ct = Counter(t)：t中各字符的目标频次。cs = defaultdict(int)：当前窗口内各字符的实际频次。cnt：当前窗口内有多少种字符的频次已经达到目标值（注意：一个字符达到目标后，即使再多出现，cnt也不会增加，因为该字符已经”达标”）。j：窗口左边界。
算法流程：
- 右指针
i遍历s，将s[i]加入窗口：- 如果加入前
cs[c] < ct[c]，说明这个字符的加入让我们朝着目标前进了一步，cnt += 1。 cs[c] += 1。
- 如果加入前
- 窗口可能包含了多余的字符——左侧某些字符的出现次数超过了
t中的要求。此时不断右移左指针j，将cs[s[j]] -= 1，直到cs[s[j]]不再超过ct[s[j]]。 - 当
cnt == len(t)时（所有字符类型都已达标），当前窗口是一个合法覆盖。检查窗口长度是否比已有最优解更短，若是则更新res。
from collections import Counter, defaultdict
class Solution: def minWindow(self, s: str, t: str) -> str: cs = defaultdict(int) ct = Counter(t) cnt = j = 0 res = ''
for i, c in enumerate(s): if cs[c] < ct[c]: cnt += 1 cs[c] += 1 while j < i and cs[s[j]] > ct[s[j]]: cs[s[j]] -= 1 j += 1 if cnt == len(t) and (res == '' or i - j + 1 < len(res)): res = s[j: i + 1]
return res关键细节解析
为什么用 cnt 而不是直接比较两个字典？
每次检查 cs 是否覆盖 ct 需要遍历 ct 的所有键，最坏 （字符集大小）。虽然对英文字母来说是常数，但有了 cnt，判断合法性变成 ——只需检查 cnt == len(t)。cnt 的维护也非常轻量：只在新字符”从不足到达标”的瞬间 +1，之后该字符再多出现也不会重复计数。
while 循环为什么是 cs[s[j]] > ct[s[j]]？
当左侧字符在窗口中的出现次数超过目标次数时，把它丢掉不会影响窗口的合法性——因为丢掉之后该字符的计数仍然 ≥ 目标值。但如果 cs[s[j]] == ct[s[j]]，丢掉它就会让该字符从达标变成不达标，窗口不再合法。因此 while 只在”多了”的时候收缩，保留恰好达标的左边界。
cnt == len(t) 的含义
cnt 记录的是「窗口中有多少个字符对覆盖 t 做出了贡献」。对于 t = "ABC"，需要 3 个字符各贡献一次，cnt 达到 3 即表示三个字符均已出现。如果 t = "AAB"，len(t) = 3，cnt 的累积过程为：第一个 A 使 cnt=1，第二个 A 使 cnt=2，B 使 cnt=3。此时 cnt == len(t)，表示 t 中的每一个字符都在窗口中被匹配上了。
执行过程追踪
以 s = "ADOBECODEBANC"，t = "ABC" 为例，追踪算法的关键步骤：
i | c | cnt 变化 | cs（关键变化） | while 收缩 | j | 窗口 [j,i] | cnt==3? | res 更新 |
|---|---|---|---|---|---|---|---|---|
| 0 | A | 0→1 | A:1 | — | 0 | [0,0]="A" | 否 | — |
| 1 | D | — | D:1 | — | 0 | [0,1]="AD" | 否 | — |
| 2 | O | — | O:1 | — | 0 | [0,2]="ADO" | 否 | — |
| 3 | B | 1→2 | B:1 | — | 0 | [0,3]="ADOB" | 否 | — |
| 4 | E | — | E:1 | — | 0 | [0,4]="ADOBE" | 否 | — |
| 5 | C | 2→3 | C:1 | — | 0 | [0,5]="ADOBEC" | 是 | "ADOBEC" (len=6) |
| 6 | O | — | O:2 | — | 0 | [0,6] | 是 | — (len=7) |
| 7 | D | — | D:2 | — | 0 | [0,7] | 是 | — (len=8) |
| 8 | E | — | E:2 | — | 0 | [0,8] | 是 | — (len=9) |
| 9 | B | — | B:2 | — | 0 | [0,9] | 是 | — (len=10) |
| 10 | A | — | A:2 | A:2→1, D:2→1, O:2→1, B:2→1, E:2→1, j 到 5 | 5 | [5,10]="CODEBA" | 是 | — (len=6) |
| 11 | N | — | N:1 | — | 5 | [5,11] | 是 | — (len=7) |
| 12 | C | — | C:2 | C:2→1, O:1→0, D:1→0, E:1→0, j 到 9 | 9 | [9,12]="BANC" | 是 | "BANC" (len=4) |
最终答案为 "BANC"，长度 4。
表中的关键转折点在 i=10：第二个 A 进入窗口后，cs['A']=2 > ct['A']=1 触发了 while 循环，左指针 j 连续收缩，将前面累积的多余字符全部清除，窗口从 [0,10] 缩至 [5,10]。类似地，i=12 时第二个 C 入窗，再次触发批量收缩，左指针从 5 一路跳到 9，找到了更短的合法窗口 "BANC"。
为什么左指针能一口气跳过这么多字符？ 因为在 j=0~4 的位置，每个字符的窗口计数都超过了目标计数（如 D、O、E 根本不在 t 中，计数永远是超的），所以 while 循环会连续执行，直到碰到一个”刚好达标”的字符才停下。这让窗口始终保持在恰好覆盖 t 的最小左边界。
复杂度
- 时间复杂度：，右指针
i遍历一次s，左指针j每个字符最多被丢弃一次，每个字符入窗出窗各 。 - 空间复杂度：，
cs和ct哈希表最多存储字符集大小的键值对。本题字符集为大小写英文字母，共 52 个，可视为 。
解题思路（need 计数法）
上一节用 cnt 统计「达标的字符贡献数」。另一种常见的实现是用 need 变量统计「还需要多少个字符才算覆盖」。思路对称，但收缩条件略有不同：
维护 need = len(t) 表示窗口还需要多少个有效字符。右扩时，若 cs[c] < ct[c]，说明这个字符是”有效”的，need -= 1。当 need == 0 时窗口合法，此时从左侧收缩：只有把左侧字符丢掉之后窗口仍然合法（即 cs[s[j]] > ct[s[j]]），才允许收缩。尝试收缩到不能再缩为止，记录结果，然后强制左移一位以寻找下一个合法窗口。
from collections import Counter, defaultdict
class Solution: def minWindow(self, s: str, t: str) -> str: cs = defaultdict(int) ct = Counter(t) need = len(t) j = 0 res = ''
for i, c in enumerate(s): cs[c] += 1 if cs[c] <= ct[c]: need -= 1
while need == 0: if res == '' or i - j + 1 < len(res): res = s[j: i + 1] # 尝试收缩左侧 cs[s[j]] -= 1 if cs[s[j]] < ct[s[j]]: need += 1 j += 1
return res两种写法的差异：
| 对比项 | cnt 计数法 | need 计数法 |
|---|---|---|
| 计数方向 | 从 0 递增到 len(t) | 从 len(t) 递减到 0 |
while 条件 | cs[s[j]] > ct[s[j]]（超频才缩） | need == 0（合法就缩） |
| 收缩粒度 | 只缩多余字符，窗口自动维持在”恰好覆盖”的最小左边界 | 缩到刚好不合法，需要手动回退 |
更新 res 时机 | 收缩完成后检查 | 收缩循环内每步检查 |
| 可读性 | 逻辑更集中，适合滑动窗口初学者 | 更接近”最小覆盖”的直觉 |
两种写法时间复杂度均为 ，选择哪种取决于个人偏好。cnt 计数法的优势在于 while 条件简单（只判断一次字符超频），且更新 res 只在外层循环的一个位置；need 计数法在 while 循环内更新 res，但不需要在外层循环再判断。
代码优化
算法层面 已是最优——至少需要遍历 s 一次才能知道哪些字符出现。以下优化聚焦于常数因子和代码简洁度。
用数组替代哈希表
题目保证 s 和 t 仅由英文字母组成（大小写均可），共 52 个可能字符。可以申请长度 128 的数组（覆盖 ASCII 英文字母范围），用 ord(c) 做下标，比 defaultdict 的哈希查找更快：
class Solution: def minWindow(self, s: str, t: str) -> str: cs = [0] * 128 ct = [0] * 128 for c in t: ct[ord(c)] += 1
cnt = j = 0 res = '' target = len(t)
for i, c in enumerate(s): idx = ord(c) if cs[idx] < ct[idx]: cnt += 1 cs[idx] += 1 while j < i and cs[ord(s[j])] > ct[ord(s[j])]: cs[ord(s[j])] -= 1 j += 1 if cnt == target and (res == '' or i - j + 1 < len(res)): res = s[j: i + 1]
return res数组访问比哈希表快（省去哈希计算和冲突解决），空间固定为 。如果确定只有小写字母（如某些变体题目），可缩至 26。
提前终止优化
如果右指针 i 已经遍历到末尾，且当前窗口已不可能比已有最优解更短，可以提前 break。但由于滑动窗口本身就保证每个字符只访问常数次，这个优化的实际收益不大，反而增加代码复杂度——可作为思路提及。
边界情况快判
添加两个快速返回判断：
if len(s) < len(t): return ""if s == t: return s这些判断在主算法之前执行，能在极端输入下省去不必要的滑动窗口过程。
总结
「最小覆盖子串」是滑动窗口的经典题型，也是面试中的高频题目。相比「无重复字符的最长子串」（找最长合法窗口）和「找到字符串中所有字母异位词」（找固定长度合法窗口），本题要求找最短合法窗口，是「可变长度 + 最优解追踪」的组合：
- 右扩：无条件扩展，同时维护贡献计数
cnt。 - 左缩：当窗口包含多余字符时，持续收缩直到恰好覆盖。
- 更新：收缩后检查是否更短，更新全局最优。
掌握本题的 cnt 计数法后，类似的「覆盖」「包含」类滑动窗口题目（如至多包含 个不同字符的最长子串、包含所有给定字符的最短子串等）都可以用同一套模板解决——只需调整 cnt 的判断条件和 while 的收缩条件即可。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时