【力扣100题】63.最小覆盖子串

题目描述

给你两个字符串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.length
• n == t.length
• 1 <= m, n <= 10^5
• s 和 t 由英文字母组成

进阶：
你能设计一个在 O(m + n) 时间内解决此问题的算法吗？

解题思路总览

一、核心解法：滑动窗口（双指针）

核心思想

使用滑动窗口的思想，维护一个包含 t 中所有字符的窗口：

1. 右指针扩张，直到窗口包含 t 中所有字符 2. 收缩左指针，找到最短的满足条件的窗口 3. 记录答案，继续扩张右指针

关键洞察

滑动窗口的关键： 1. 右指针不断右移，扩大窗口 2. 当窗口满足条件时，收缩左指针尝试优化 3. 使用两个哈希表： - need: t 中每个字符需要的次数 - window: 当前窗口中每个字符出现的次数 当 window 满足 need 时，说明窗口有效。

图解

s = "ADOBECODEBANC", t = "ABC" need = {A:1, B:1, C:1} 滑动窗口过程： 初始状态: left=0, right=0 window = {} needCnt = 3 扩张 right=0, s[0]='D': D 不在 need 中，跳过 扩张 right=1, s[1]='D': D 不在 need 中，跳过 扩张 right=2, s[2]='O': O 不在 need 中，跳过 扩张 right=3, s[3]='B': B 在 need 中 window[B]=1, need[B]=1, count=1 count=3? 否，继续扩张 扩张 right=4, s[4]='E': E 不在 need 中，跳过 扩张 right=5, s[5]='C': C 在 need 中 window[C]=1, need[C]=1, count=2 扩张 right=6, s[6]='O': O 不在 need 中，跳过 扩张 right=7, s[7]='D': O 不在 need 中，跳过 扩张 right=8, s[8]='E': E 不在 need 中，跳过 扩张 right=9, s[9]='B': B 在 need 中 window[B]=2, need[B]=1, count=2 (B已经满足，不增加count) 扩张 right=10, s[10]='A': A 在 need 中 window[A]=1, need[A]=1, count=3 count=3 == need.size()，窗口有效！ 收缩 left: left=0: 窗口 [0,10] = "ADOBECODEBA" 不满足，收缩 left=1 left=1: 窗口 [1,10] = "DOBECODEBA" 不满足，收缩 left=2 ... left=9: 窗口 [9,10] = "BA" 满足！记录答案 "BA"，长度=2 left=10: 收缩，窗口 [10,10] = "A" 不满足，继续扩张 继续扩张 right=11, s[11]='N': N 不在 need 中，跳过 扩张 right=12, s[12]='C': C 在 need 中 window[C]=2, need[C]=1, count=3 (C已满足) 窗口有效！ 收缩 left: left=10: 窗口 [10,12] = "ANC" 不满足，收缩 left=11 left=11: 窗口 [11,12] = "NC" 不满足，收缩 left=12 left=12: 窗口 [12,12] = "C" 不满足，收缩 left=13 right 到达末尾，停止 答案: "BANC"（长度为4，比 "BA" 更长但更靠后）

二、算法流程图

输入: s = "ADOBECODEBANC", t = "ABC" 初始化: need = {A:1, B:1, C:1} window = {} left = 0, right = 0 count = 0 (已满足的字符种类数) minLen = INF, start = 0 扩张 right=3 (遇到B): window[B]++, count=1 扩张 right=5 (遇到C): window[C]++, count=2 扩张 right=10 (遇到A): window[A]++, count=3 窗口有效！count == need.size() 收缩 left: left=0 -> "ADOBECODEBA" 无效 left=1 -> "DOBECODEBA" 无效 ... left=9 -> "BA" 有效！记录 minLen=2, start=9 left=10 -> "A" 无效 继续扩张 right=12 (遇到C): window[C]++, count=3 窗口有效！ 收缩 left: left=11 -> "ANC" 无效 left=12 -> "C" 无效 right 到达末尾，结束 输出: "BANC" (start=9, minLen=4)

三、完整代码实现

classSolution{public:stringminWindow(string s,string t){unordered_map<char,int>need,window;// 记录 t 中每个字符需要的次数for(charc:t){need[c]++;}intleft=0,right=0;intcount=0;// 已满足的字符种类数intstart=0,minLen=INT_MAX;while(right<s.size()){charc=s[right++];// 如果字符在 need 中，加入 windowif(need.count(c)){window[c]++;// 当 window[c] 达到 need[c] 时，count++if(window[c]==need[c]){count++;}}// 当窗口满足条件时，收缩左边界while(count==need.size()){// 更新最小窗口if(right-left<minLen){start=left;minLen=right-left;}// 收缩左边界chard=s[left++];// 如果字符在 need 中，从 window 中移除if(need.count(d)){// 注意：先判断再--if(window[d]==need[d]){count--;// 移除后不再满足}window[d]--;}}}returnminLen==INT_MAX?"":s.substr(start,minLen);}};

四、逐行解析

unordered_map<char,int>need,window;

• need：记录 t 中每个字符需要的次数
• window：记录当前窗口中每个字符出现的次数

for(charc:t){need[c]++;}

• 初始化 need，统计 t 中每个字符出现的次数

intleft=0,right=0;intcount=0;intstart=0,minLen=INT_MAX;

• left, right：滑动窗口的左右边界
• count：当前窗口中已满足 need 条件的字符种类数
• start, minLen：最小窗口的起始位置和长度

while(right<s.size()){charc=s[right++];

• 右指针不断右移，扩张窗口

if(need.count(c)){window[c]++;if(window[c]==need[c]){count++;}}

• 如果当前字符在 need 中，加入 window
• 当 window[c] 达到 need[c] 时，count++（这个字符已经满足条件）

while(count==need.size()){

• 当窗口满足条件时（count == need.size()），收缩左边界尝试优化

if(right-left<minLen){start=left;minLen=right-left;}

• 更新最小窗口

chard=s[left++];if(need.count(d)){if(window[d]==need[d]){count--;}window[d]--;}

• 收缩左边界
• 如果移除的字符在 need 中，先判断是否会让 count 减少
• 然后从 window 中移除该字符

五、count 变量的作用

count 表示当前窗口中满足 need 条件的字符种类数。 例如 t = "ABC"，need = {A:1, B:1, C:1} 初始: count = 0 遇到 A: window[A]=1 == need[A], count=1 遇到 B: window[B]=1 == need[B], count=2 遇到 C: window[C]=1 == need[C], count=3 当 count == need.size() 时，说明所有字符都满足了条件。 收缩时： 移除 A: window[A]=0 != need[A], count 不变 移除 B: window[B]=0 != need[B], count 不变 移除 C: window[C]=0 != need[C], count-- (变为2) count-- 只发生在 window[d] == need[d] 时，即移除后刚好不再满足。

六、与第 567 题（字符串的排列）对比

七、复杂度分析

详细分析：

时间复杂度： right 指针最多移动 m 次 left 指针最多移动 m 次 每次移动都是 O(1) 操作 总计：O(2m) = O(m) 空间复杂度： need 和 window 最多存储 128 个字符（ASCII） O(1)（常数空间）

八、边界情况分析

示例：t 有重复字符

s = "AAAB", t = "AAB" need = {A:2, B:1} 扩张过程： 遇到 A: window[A]=1, need[A]=2, count=0 遇到 A: window[A]=2, need[A]=2, count=1 遇到 A: window[A]=3, count=1 (已达标不再增加) 遇到 B: window[B]=1, need[B]=1, count=2 count=2 == need.size()=2，窗口有效 收缩： 移除第一个 A: window[A]=2, count=2 (仍满足) 移除第二个 A: window[A]=1, need[A]=2, count-- (变为1) 窗口无效，继续扩张

九、面试追问 FAQ

十、相关题目

十一、总结

最小覆盖子串是滑动窗口的经典问题，通过维护一个满足 need 条件的窗口，并不断收缩优化，实现了 O(m + n) 的时间复杂度。