最小覆盖子串：解题思路与代码分析

问题描述

在给定的字符串 s 中，找到包含字符串 t 所有字符的最小子串。如果 s 中没有这样的子串，则返回空字符串 ""。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
输入：s = "a", t = "aa"
输出：""
解释：t 中的字符 'a' 有两个，而 s 中只有一个字符 'a'，因此没有符合条件的子串，返回空字符串。

题目要求：

对于 t 中重复的字符，最小覆盖子串中该字符数量必须不少于 t 中该字符的数量。
最优解的时间复杂度应为 O(m+n)，其中 m 是 s 的长度，n 是 t 的长度。

解题思路

此问题可以通过 滑动窗口 技巧来有效解决，使用双指针和哈希表来判断窗口是否包含所有字符。

滑动窗口算法

滑动窗口是一种常用于解决此类“子串”问题的技巧。基本思路是：

使用两个指针 left 和 right，分别表示当前窗口的左右边界。
通过右指针不断扩展窗口，直到窗口包含了所有 t 中的字符。
当窗口有效时，尝试通过左指针收缩窗口，来获取最小的覆盖子串。

为了跟踪窗口中的字符，我们使用两个哈希表：

count_t：存储字符串 t 中字符的频率。
count_s：存储当前窗口中字符的频率。

关键点：

窗口中的字符需要包含 t 中所有字符，并且字符的数量要满足 t 中对应字符的频率。
当窗口满足条件时，尝试收缩窗口，更新最小覆盖子串。

代码实现

from collections import Counterclass Solution:def minWindow(self, s: str, t: str) -> str:ans_left, ans_right = -1, len(s)left = 0count_s = Counter()  # 当前窗口中的字符频率count_t = Counter(t)  # 目标字符串 t 中的字符频率# 记录 t 中需要的字符数量required = len(count_t)formed = 0  # 当前窗口满足的字符种类数# 滑动窗口遍历for right, x in enumerate(s):# 将右边字符加入窗口count_s[x] += 1# 如果窗口中的字符数量与 t 中的字符数量匹配，更新 formedif count_s[x] == count_t[x]:formed += 1# 当窗口包含所有 t 中的字符时，尝试收缩左边界while formed == required:if right - left < ans_right - ans_left:ans_left, ans_right = left, right# 收缩窗口，减小窗口左边界count_s[s[left]] -= 1if count_s[s[left]] < count_t[s[left]]:formed -= 1left += 1# 如果找到了符合条件的子串，返回它；否则返回空字符串return "" if ans_left == -1 else s[ans_left:ans_right + 1]

代码解析

变量初始化：
- ans_left 和 ans_right 用来记录最小覆盖子串的左右边界。
- count_s 用于存储当前窗口中字符的频率。
- count_t 用于存储字符串 t 中字符的频率。
- required 记录 t 中不同字符的数量。
- formed 记录当前窗口中满足 t 中字符频率要求的字符种类数。
遍历字符串 s：
- 对于每个字符 x，增加 count_s[x]。
- 如果 count_s[x] 达到 count_t[x]，表示窗口中字符 x 的数量满足要求，formed 增加。
窗口收缩：
- 当 formed == required 时，表示当前窗口已经包含了 t 的所有字符，可以尝试通过左指针收缩窗口。
- 在收缩过程中，更新最小覆盖子串的边界，并根据 count_s[s[left]] 是否小于 count_t[s[left]] 来判断是否减少 formed。
返回结果：
- 如果找到满足条件的子串，返回其子串；否则返回空字符串。