76. 最小覆盖子串

76. 最小覆盖子串

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

• m == s.length

• n == t.length

• 1 <= m, n <= 105

• s 和 t 由英文字母组成

1. 初始化

• 使用 need 哈希表记录目标字符串 t 中每个字符需要的数量

• 使用 window 哈希表记录当前窗口中每个字符的数量

• 使用 valid 变量记录当前已经满足条件的字符个数

2. 滑动窗口过程

扩大窗口

• 右指针 i 不断向右移动，将新的字符加入窗口

• 每当加入一个字符，更新 window 中对应字符的计数

• 如果该字符是所需字符且数量未超过需求，则 valid 计数加1

收缩窗口

• 当某个字符的数量超过所需时，左指针 j 向右移动

• 移动过程中更新 window 中对应字符的计数

更新结果

• 当 valid == t.size() 时，说明找到一个可行解

• 如果当前可行解的长度小于之前找到的最小长度，则更新结果

3. 时间复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串 s 的长度

• 空间复杂度：O(k)，其中 k 为字符集大小，本题中字符集为英文字母，所以 k = 26

4. 关键点

• 使用哈希表维护窗口中字符的频次

• 使用 valid 变量避免重复检查是否满足条件

• 左右指针的移动策略保证了找到最小覆盖子串