LeetCode 题解工作台
最小覆盖子串
给定两个字符串 s 和 t ，长度分别是 m 和 n ，返回 s 中的 最短窗口 子串 ，使得该子串包含 t 中的每一个字符（ 包括重复字符 ）。如果没有这样的子串，返回空字符串 "" 。 测试用例保证答案唯一。 示例 1： 输入： s = "ADOBECODEBANC", t = "ABC" 输出…
3
题型
7
代码语言
3
相关题
当前训练重点
困难 · 滑动窗口（状态滚动更新）
答案摘要
我们用一个哈希表或数组 统计字符串 中每个字符出现的次数，用另一个哈希表或数组 统计滑动窗口中每个字符出现的次数。另外，定义两个指针 和 分别指向窗口的左右边界，变量 表示窗口中已经包含了 中的多少个字符，变量 和 分别表示最小覆盖子串的起始位置和长度。 我们从左到右遍历字符串 ，对于当前遍历到的字符 ：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 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 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在
O(m + n) 时间内解决此问题的算法吗？解题思路
方法一：计数 + 双指针
我们用一个哈希表或数组 统计字符串 中每个字符出现的次数，用另一个哈希表或数组 统计滑动窗口中每个字符出现的次数。另外，定义两个指针 和 分别指向窗口的左右边界，变量 表示窗口中已经包含了 中的多少个字符，变量 和 分别表示最小覆盖子串的起始位置和长度。
我们从左到右遍历字符串 ，对于当前遍历到的字符 ：
- 我们将其加入窗口中，即 ，如果此时 ，则说明 是一个「必要的字符」，我们将 加一。
- 如果 等于 的长度，说明此时窗口中已经包含了 中的所有字符，我们就可以尝试更新最小覆盖子串的起始位置和长度了。如果 ，说明当前窗口表示的子串更短，我们就更新 和 。
- 然后，我们尝试移动左边界 ，如果此时 ，则说明 是一个「必要的字符」，移动左边界时会把 这个字符从窗口中移除，因此我们需要将 减一，然后更新 ，并将 右移一位。
- 如果 与 的长度不相等，说明此时窗口中还没有包含 中的所有字符，我们就不需要移动左边界了，直接将 右移一位，继续遍历即可。
遍历结束，如果没有找到最小覆盖子串，返回空字符串，否则返回 即可。
时间复杂度 ，空间复杂度 。其中 和 分别是字符串 和 的长度；而 是字符集的大小，本题中 。
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
window = Counter()
cnt = l = 0
k, mi = -1, inf
for r, c in enumerate(s):
window[c] += 1
if need[c] >= window[c]:
cnt += 1
while cnt == len(t):
if r - l + 1 < mi:
mi = r - l + 1
k = l
if need[s[l]] >= window[s[l]]:
cnt -= 1
window[s[l]] -= 1
l += 1
return "" if k < 0 else s[k : k + mi]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you correctly expand and contract the window without rescanning characters?
- question_mark
Can you handle repeated characters in t when updating the hashmap counts?
- question_mark
Will you return the empty string when no valid window exists instead of partial matches?
常见陷阱
外企场景- error
Failing to account for duplicate characters in t, which can result in windows that appear valid but are missing counts.
- error
Not contracting the window from the left, returning a larger substring instead of the minimum window.
- error
Using inefficient nested loops, leading to O(m*n) behavior instead of the linear sliding window approach.
进阶变体
外企场景- arrow_right_alt
Return the length of the minimum window substring instead of the substring itself.
- arrow_right_alt
Find the minimum window containing all distinct characters of t ignoring duplicates.
- arrow_right_alt
Determine the minimum window substring in s that covers a subset of t's characters under a given frequency threshold.