最小覆盖子串：从枚举到滑动窗口的完整推导与实现

有一类字符串题，面试官一说出来，大部分人的第一反应就是枚举：给你字符串s和t，在s里找出包含t所有字符的最短子串。这就是 LeetCode 第 76 题「最小覆盖子串」，通常被标成 Hard，但题目本身并不难，难的是你愿不愿意从“枚举所有子串”一步步优化到“滑动窗口”。我面试时见过这道题，也陪朋友练过很多遍，今天这篇就完整拆一下：先讲最笨但最好懂的枚举法，再讲标准滑动窗口的推导过程、实现细节和边界坑，最后聊面试时怎么一步步把思路讲顺。

如果你正在准备算法面试，或者刷题刷到字符串双指针部分卡住了，这篇文章会给你一套能直接复现、能照抄的完整方案。通篇围绕“最小覆盖子串”这一个点讲透，不扯虚的。

1. 先把题意吃透：什么叫做“覆盖”，什么叫做“最小”

1.1 题面复述与示例推演

题目说的是：给定两个字符串s和t，返回s中涵盖t所有字符的最小子串。如果s里不存在这样的子串，返回空字符串。注意“涵盖”是关键词：窗口里每个字符出现的次数，必须都不少于t里该字符出现的次数。

举个例子，s = "ADOBECODEBANC"，t = "ABC"。肉眼扫一遍，能包含A、B、C的子串不少：

• "ADOBEC"，长度 6；
• "CODEBA"，长度 6；
• "BANC"，长度 4；
• "ANC"不行，缺 B。

最短的就是"BANC"。为什么不是更靠前的"ADOBEC"？因为它虽然包含了三个目标字符，但长度更长。我们要的“最小”是在所有合法覆盖子串里取长度最小的那个，不是找第一个出现的。多个答案长度相同且都合法时，返回任意一个即可，判题器会接受。

另外，题目默认大小写敏感，'a'和'A'是两个完全不同的字符。这一点别看轻了，很多人在手写用例时忽略掉，等跑起来才发现自己的窗口把大小写混在一起统计了。

1.2 一个容易掉进去的坑：t 里字符重复怎么办

“覆盖”这个词容易让人想到集合，但是t里的字符可能会重复。比如t = "aa"，那s的窗口里至少要有两个'a'，只有一个'a'是不能算覆盖的。

这是很多初学者写错的地方：用set(t)去判断窗口里有没有这些字符，直接忽略次数要求。对t = "aa"这种输入，window里只要出现一个'a'，set判断就通过了，但正确答案应该是一个长度为 2、包含两个'a'的窗口。

所以，判断覆盖状态的核心一定基于字符计数，而不是简单查一下 HashSet。这也是后面所有方案都离不开计数器的原因。牢牢记住：count(window[c]) >= count(t[c])才是合法覆盖。窗口里可以比t需要的字符多，比如t = "aa"，窗口"aaa"是合法覆盖，因为a的数量 3 不小于 2。

1.3 写代码前先确认边界条件

我刷题的习惯是：先想边界，再写主体。这道题的边界条件主要是这几个：

1. s或t为空：直接返回空字符串。
2. len(s) < len(t)：s总长度都不够，肯定不可能覆盖，返回空字符串。
3. t中所有字符在s里根本凑不齐，返回空字符串。
4. s和t长度都为 1，且字符相同：返回s自身。
5. t长度很短但s很长，比如s = "aaaa...a"，t = "a"：任意一个单字符窗口都合法，返回哪个都行，常见代码会返回最左边那个。

把边界在草稿纸上列一遍再动手，后面实现起来会稳很多。很多提交在 LeetCode 上 WA，不是主逻辑错，而是空字符串、找不到这类兜底没做好。

2. 枚举法：最笨但最能解释清楚的方法

2.1 枚举起点：固定 i，向右找第一个满足的 j

第一种最直觉的做法：枚举子串的起始下标i，然后让j从i向右移动，一边移动一边维护窗口里各字符的计数；一旦当前窗口已经覆盖了t，就停住，记录这个窗口的长度，再换下一个i。

为什么j第一次满足条件就停？因为j再往右走，窗口只会更长，不可能比当前这个更优。所以对固定起点i来说，第一个覆盖点就是最优解。代码写出来长这样：

from collections import Counter def min_window_enum_start(s: str, t: str) -> str: if not s or not t or len(s) < len(t): return "" need = Counter(t) ans = "" for i in range(len(s)): window = {} for j in range(i, len(s)): window[s[j]] = window.get(s[j], 0) + 1 if all(window.get(ch, 0) >= need[ch] for ch in need): if ans == "" or (j - i + 1) < len(ans): ans = s[i:j + 1] break return ans

all(...)每次检查t里所有字符是否都满足数量要求。这个写法正确性一目了然，和小白解释“什么叫覆盖”特别好使。但它的代价是，每换一个起点i，都要重新从i开始累加计数，前一个窗口统计过的字符全部浪费掉了。

2.2 枚举长度：按窗口长度从短到长扫描

另一种枚举思路是按窗口长度来。窗口最短不可能短于len(t)，最长是len(s)。于是从小到大枚举长度L，在每个长度下，用窗口左端点i滑过整个s，检查所有长度为L的子串，只要找到一个合法的就返回，因为越短的越早被发现。

from collections import Counter def min_window_enum_len(s: str, t: str) -> str: if not s or not t or len(s) < len(t): return "" need = Counter(t) for L in range(len(t), len(s) + 1): for i in range(0, len(s) - L + 1): sub = s[i:i + L] window = Counter(sub) if all(window.get(ch, 0) >= need[ch] for ch in need): return sub return ""

这段比 2.1 还好理解，但每次切sub都生成新字符串，底层又是一次 O(L) 的复制。如果s长度是 10^5，这个方案基本不可能跑完。不过作为“正确答案的验证器”，在随机小规模测试里对照滑动窗口的输出，非常有用。

2.3 枚举法的复杂度账本：切片是隐性炸弹

枚举起点的方案最坏要枚举 O(n^2) 个窗口，每个窗口做一次覆盖检查。如果t的字符种类数是k，检查all(...)就是 O(k)。总复杂度可以粗估为 O(n^2 * k)。

这里有个很多人忽略的点：切片很贵。如果在循环里面频繁写s[i:j+1]，每次切片都是 O(len) 的复制，会直接把 O(n^2) 拉高到 O(n^3)。所以在枚举代码里，我只在找到答案之后才切一次，中间只记录下标和长度。这一点对后面优化版本同样适用，能不用切片就不用切片。

枚举法有没有机会过？如果s很短，比如几百个字符，t也很短，那它可以秒过。我自己在本地做随机测试时，反而会专门留一份枚举法代码，用来和滑动窗口版本对拍，确保优化后的代码没有改错逻辑。它作为“思路垫脚石”的价值远大于作为“最终提交方案”的价值。

3. 滑动窗口的推导：从“重复扫描”到“一把尺子来回量”

3.1 观察到问题本质：很多计数是重复劳动

再看 2.1 的枚举起点法。以s = "ADOBECODEBANC",t = "ABC"为例：

• 起点i = 0时，窗口扫到"ADOBEC"才覆盖，j = 5；
• 起点i = 1时，窗口从"D"开始重新数，又要一直扫到j = 10附近才覆盖；
• 起点i = 2时，窗口从"O"开始，又是重新数。

但i = 1的窗口和i = 0的窗口，有很大一段是重叠的。i = 1的窗口在覆盖前，只不过是把i = 0窗口的头部字符'A'去掉，再往后补几个新字符而已。既然这样，为什么要从零开始重建计数呢？

这就是滑动窗口的第一层动机：复用上一次窗口的统计结果。右指针每前进一格，只需要把新字符的计数加 1；左指针每前进一格，只需要把离开窗口的字符计数减 1。这样每个字符只被加一次、减一次，总工作量从 O(n^2) 降到 O(n)。

3.2 关键论证：为什么左右指针都可以只往右走

有了两端的指针之后，很多人会担心：这样左一下右一下，会不会漏掉某些合法窗口？答案是不会，关键在于一个单调性：随着左指针 left 不断右移，能够覆盖 t 的右指针 right 的“最短合法位置”不会左移。

这句话可以这样理解：窗口去掉头部字符后，字符总数变少，覆盖能力只会下降不会上升。原本窗口覆盖t，去掉一个字符后可能就不覆盖了，那只能把 right 往右延伸去补字符。所以说，right 的移动方向是单调的，从前往后扫一遍就足够。

这个性质保证了双指针算法的完备性：任意一个最优窗口[l, r]，当 right 到达r时，left 一定已经停在某个不超过l的位置，然后 while 循环不断收缩 left，经过l的那一刻，就一定记录到了[l, r]这个窗口。整个过程中，left 和 right 各自至多移动 n 次，算法也就不会漏解。

3.3 滑动窗口的运作状态机

用一句话概括滑动窗口的日常：right负责扩张，扩张到覆盖为止；left负责收缩，收缩到刚好不覆盖为止。每次收缩前，当前窗口是一个合法覆盖，记录它的长度；一旦收缩后不再覆盖，就停下来，让right继续往前走。

可以把它看成一个循环往复的过程：

1. right不断右移，把字符纳入窗口，更新计数；
2. 当窗口已经覆盖t，进入收缩阶段；
3. 在收缩循环里，先记录当前窗口，再把left右移、更新计数；
4. 如果收缩后仍然覆盖，继续收缩；如果不覆盖，退出循环；
5. right继续右移，重复整个过程。

每一步都是 O(1) 的计数更新，整个算法的代价就是两个指针总共扫过一遍字符串，复杂度 O(n)。这就是“枚举所有子串”到“利用单调性只遍历必要窗口”的优化本质。

4. 标准滑动窗口实现：计数器、missing 值与收缩时机

4.1 计数器设计：固定数组还是哈希表

实现之前先决定怎么存。t里的字符无非 ASCII 范围内的字母和符号，LeetCode 原题通常也只给英文字母。最省事的方式是开一个长度为 128 的数组，直接把字符转成 ASCII 下标，need记录t的需求，window记录当前窗口的实际计数：

• 为什么是 128？ASCII 范围 0~127，包含所有常见英文字符，直接ord(ch)取下标。
• 如果题目明确只有大写/小写字母，可以压缩到 52 长度再映射，但没必要，128 已经是常数级空间。
• 如果字符集可能很大（比如 Unicode），数组就不合适了，用Counter或defaultdict更稳。

判断覆盖状态时，如果每次都用all(...)比较两个 Counter，复杂度又要乘上字符种类数。更好的办法是维护一个整数状态量，常见两种写法：

写法 A：missing 总数设missing = len(t)，表示窗口还缺多少个字符。每次右指针纳入字符c时，如果window[c] < need[c]，说明这个字符补上了一个缺口，missing -= 1。左指针收缩时反向处理。

写法 B：formed 种类数设need_size = len(need)，表示t里有几种字符。当窗口里某种字符的数量从小于need[c]变成刚好等于need[c]时，formed += 1。当formed == need_size时，窗口覆盖t。

两种写法都可以，我下面主要用写法 B，因为它和“每种字符是否达标”的语义更贴近，不容易在字符数量超过需求时算错账。

4.2 formed 计数的精确条件：必须是等于，不是大于等于

写法 B 有个细节极其容易写错。右指针纳入字符c后，更新窗口计数的同时，判断：

if window[c] == need[c]: formed += 1

这里必须是==，不能是>=。原因是：formed只统计“从没达标变成刚好达标”的那一次。假如need['a'] = 2，窗口里'a'的数量从 2 变成 3 时，'a'本来就达标了，不能再让formed加 1，否则formed会超过need_size，破坏判断逻辑。

对应的，左指针收缩时，窗口计数的更新顺序是：先把window[c] -= 1，然后判断：

if window[c] < need[c]: formed -= 1

也就是说，只有当字符数量从达标变成不达标时，formed才减 1。注意要先减计数再判断，顺序反了会得到错误结果。

4.3 完整可提交的 Python 实现

from collections import Counter def minWindow(s: str, t: str) -> str: if not s or not t or len(s) < len(t): return "" need = Counter(t) window = Counter() need_size = len(need) formed = 0 left = 0 min_len = float("inf") start = 0 for right, char in enumerate(s): window[char] += 1 if window[char] == need[char]: formed += 1 while formed == need_size: if right - left + 1 < min_len: min_len = right - left + 1 start = left left_char = s[left] window[left_char] -= 1 if window[left_char] < need[left_char]: formed -= 1 left += 1 return "" if min_len == float("inf") else s[start:start + min_len]

逐个注意点过一遍：

• window里统计了所有出现在s中的字符，包括不在t里的字符。这些多余字符是否会干扰formed？不会，因为need['X'] = 0，window['X']永远不可能等于 0（只要它进了窗口就至少是 1），所以==条件不成立，不会误加formed。
• while循环退出条件必须是formed == need_size。只要达标就收缩，收缩到不达标才停，因为我们要找最短窗口，能缩就缩。
• 记录答案的位置在收缩循环体内，每缩一步都记录一次，这样不会错过“中间某个更短但依然合法”的窗口。
• 找不到时min_len依然是inf，最后返回空串。这里不要马虎写成返回None，题面要求是空字符串。

4.4 C++ 版本：面试中常见的写法

如果你面的是 C++ 岗位，或者刷题时习惯用 C++，下面这份可以直接背：

class Solution { public: string minWindow(string s, string t) { if (s.empty() || t.empty() || s.size() < t.size()) return ""; vector<int> need(128, 0), window(128, 0); for (char c : t) need[c]++; int needSize = 0; for (int i = 0; i < 128; i++) { if (need[i] > 0) needSize++; } int formed = 0; int left = 0; int minLen = INT_MAX; int start = 0; for (int right = 0; right < s.size(); right++) { char c = s[right]; window[c]++; if (window[c] == need[c]) formed++; while (formed == needSize) { if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; } char leftChar = s[left]; window[leftChar]--; if (window[leftChar] < need[leftChar]) formed--; left++; } } return minLen == INT_MAX ? "" : s.substr(start, minLen); } };

和 Python 版逻辑完全一致。C++ 用数组当计数器，比unordered_map快不少，因为数组下标访问是 O(1) 且没有哈希开销。这也是面试官比较喜欢看到的写法。

5. 三种实现的复杂度与实测：谁在什么场景下胜出

5.1 复杂度对比表

把前面提到的方案放一起对比：

这里n是s的长度，k是t的字符种类数。标准滑动窗口里，right和left各自最多移动 n 次，每次更新都是常数级操作，所以是 O(n + k)。如果你把计数器固定成 128 长度的数组，空间复杂度其实就是 O(1)。

5.2 刁钻用例：自我验证清单

我平时写完滑动窗口，习惯用下面这批用例做回归测试：

最后一个用例值得多说一句：s = "aAbBcC"，t = "abc"。注意s里有大写A，也有小写a，但我们需要的是小写a、小写b、小写c。从下标 0 的'a'开始，窗口往下扩到下标 4 的'c'，也就是"aAbBc"，才同时包含小写a、b、c。中间没有任何一个更短的窗口能同时包含这三个小写字符，所以答案是"aAbBc"。

跑这些用例时，我通常会再放一份枚举法代码做对拍。随机生成长度不等的字符串，滑动窗口和枚举法输出应该完全一致。只要有任何一个用例不一致，基本都是formed增减条件或者收缩顺序写错了。

5.3 一种可选的进阶优化：只滑动有效位置

标准滑窗已经能过 LeetCode 原题，但面试官可能会追问一句：能不能再优化？有一个思路是——只保留s中属于t的字符位置，在这个稀疏序列上滑动窗口。

道理很简单：窗口两端只有落在t里的字符上，长度才有机会缩短。中间那些不在t里的字符，只是在计数时被动经过，最后取s的下标算长度而已。

from collections import Counter def min_window_filtered(s: str, t: str) -> str: if not s or not t or len(s) < len(t): return "" need = Counter(t) positions = [i for i, ch in enumerate(s) if ch in need] if len(positions) < len(t): return "" window = Counter() formed = 0 need_size = len(need) left_idx = 0 ans = "" for right_idx, pos in enumerate(positions): ch = s[pos] window[ch] += 1 if window[ch] == need[ch]: formed += 1 while left_idx <= right_idx and formed == need_size: left_pos = positions[left_idx] cur_len = pos - left_pos + 1 if ans == "" or cur_len < len(ans): ans = s[left_pos:pos + 1] left_ch = s[left_pos] window[left_ch] -= 1 if window[left_ch] < need[left_ch]: formed -= 1 left_idx += 1 return ans

这个版本的循环次数从n降到了“s中属于t的字符个数”。最坏情况下（s全是t里的字符）复杂度不变，但实际场景里如果s很长、目标字符很稀疏，收益非常明显。代价是代码多了一层positions，可读性稍微下降。面试讲这一版能加分，但不要为了炫技影响主版本正确性。

5.4 实测表现：大数据下的直观感受

我在本地用长度 10^5 的随机字符串、长度 1000 的随机目标串做过对比。枚举版本几分钟都跑不完，标准滑窗是毫秒级，候选位置过滤版在目标字符稀疏时还能再快一倍左右。如果你手边没有测试环境，也可以从复杂度上感受差距：枚举是 O(n^2)，滑窗是 O(n)，差了三个数量级，数据量一大就是天壤之别。

实际写线上服务时，如果不是特定场景，标准滑窗已经足够。候选位置过滤更适合“海量文本里反复匹配同一批短关键词”这种前期预处理可以复用的场景。

6. 面试怎么讲、变体怎么答

6.1 面试现场的一种推荐表达顺序

如果面试官让你现场做这道题，不建议上来就闷头写滑动窗口。更好的节奏是：

第一步，先确认题意。说清楚“覆盖”是指每个字符数量都不小于t中的数量，t可能有重复字符，大小写敏感。

第二步，抛最简单的思路。枚举起点，向右扩展到第一个覆盖点，复杂度 O(n^2 * k)，数据量大时不行。

第三步，指出问题。每次枚举起点都重新计数，大量窗口内容重叠被重复统计。

第四步，引出优化。左右指针都单调右移，窗口计数可以复用，复杂度降到 O(n)。这里可以提一句单调性：随着 left 右移，需要的 right 不会左移。

第五步，边写边讲。写need、window、formed的时候说明每个变量的含义，重点解释为什么用==判断达标。

第六步，自己跑例子。拿"ADOBECODEBANC"和"ABC"验证一下，顺手补几个边界用例。这样一套下来，比直接甩出完整代码更有说服力。

6.2 高频相似题与套路迁移

最小覆盖子串属于“滑动窗口定式”里的经典一题，它的模板稍加改动就能迁移到很多题目：

• 无重复字符的最长子串（第 3 题）：窗口内出现重复字符时收缩 left，更新的是“最长”答案。
• 字符串的排列（第 567 题）：固定窗口长度等于len(t)，检查窗口是否是t的排列。
• 找到字符串中所有字母异位词（第 438 题）：类似 567，但把所有满足条件的起点都收集起来。
• 替换后的最长重复字符（第 424 题）：窗口内除了最多字符外的其他字符数不超过 k，否则收缩。

它们的统一骨架可以概括成：

left = 0 for right in range(len(s)): 更新窗口状态 while 窗口不满足条件: 更新答案（如果是找最短） 收缩 left 更新窗口状态 更新答案（如果是找最长）

第 76 题就是典型的“收缩前更新最短答案”。理解了这个模子，面试遇到同族题目会轻松不少。

6.3 我实际刷下来的一点心得

这道题我自己刷了三遍才真正记住，不是因为代码难，而是因为某几个细节特别容易凭“感觉”写错。一个是formed必须用==触发；另一个是收缩循环里要先减计数再判断是否不达标；还有一个是边界条件的兜底。每一条是独立的小坑，单独看都简单，串在一起就很容易翻车。

我的建议是：不要只背标准答案。先把枚举法写出来，再用对拍的方式把它改成滑窗，你才能真正理解“为什么双指针能省掉这么多计算”。这道题的价值不在代码本身，而在你推导优化的过程。

如果你准备面试，还可以把这道题和 3、438、567 放在同一天刷，彼此对照。你会发现它们其实是同一把尺子在量不同的物理量——有时候量最小长度，有时候量最大长度，有时候量固定长度。在第 76 题上花的时间，会在这些相似题上连本带利赚回来。