【LeetCode 热题100】76. 最小覆盖子串的算法思路及python代码

76. 最小覆盖子串

给你一个字符串 $s$、一个字符串 $t$。返回 $s$ 中涵盖 $t$ 所有字符的最小子串。如果 $s$ 中不存在涵盖 $t$ 所有字符的子串，则返回空字符串 $‘‘"$ 。

注意：

• 对于 $t$ 中重复字符，我们寻找的子字符串中该字符数量必须不少于 $t$ 中该字符数量；
• 如果 $s$ 中存在这样的子串，我们保证它是唯一的答案。

示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

个人解题思路：

我们可以利用“滑动窗口”的思想来解决这个问题。 具体步骤如下：

初始化：

• 创建一个字典 remaining_target，记录字符串 t 中每个字符的出现次数。
• 定义两个指针 index 和 temp_index，表示当前窗口的左右边界。
• 定义变量 current_substring，用于记录当前窗口的子串。
• 定义变量 min_substring，用于记录最小子串。
• 定义变量 min_substring_length，用于记录最小子串的长度。
• 定义布尔变量 found_all_chars，表示是否已找到目标字符串的所有字符。

遍历字符串：

代码首先初始化了目标字符串 t 的临时变量 remaining_target，并设置了变量来记录当前子串和最小子串。接着，代码遍历源字符串 s，对每个字符进行判断它是否在 remaining_target 中。如果在，则表示找到了目标字符串中的一个字符，remaining_target 中对应字符的数量减一。当在s 中找到第一个 t 的元素时，代码记录下当前的索引 temp_index，以备后续滑动index使用。 在遍历过程中，代码不断更新当前子串 current_substring，并在满足条件时更新最小子串 min_substring。当 remaining_target 的长度为零时，说明当前窗口已经包含了目标字符串的所有字符，代码会通过调整索引来优化子串的长度。最终，代码返回找到的最小子串。

python代码：

class Solution:def minWindow(self, s: str, t: str) -> str:# 初始化目标字符串的副本remaining_target = t# 初始化当前子串和最小子串current_substring = ''min_substring = ''min_substring_length = len(s)# 标记是否已找到目标字符串的所有字符found_all_chars = Falseindex = 0# 如果源字符串的长度小于目标字符串，直接返回空字符串if len(s) < len(t):return ''# 遍历源字符串while index < len(s):current_char = s[index]index += 1# 如果当前字符在目标字符串中if current_char in remaining_target:found_all_chars = True# 删除目标字符串中对应的字符remaining_target = remaining_target.replace(current_char, '', 1)# 如果目标字符串中剩余字符的长度为目标字符串长度减一，记录当前索引if len(remaining_target) == len(t) - 1:temp_index = index# 如果已找到目标字符串的所有字符if found_all_chars:current_substring += current_char  # 将当前字符添加到当前子串# 如果目标字符串的所有字符都已找到且当前子串长度小于最小子串长度if len(remaining_target) == 0 and len(current_substring) <= min_substring_length:min_substring = current_substringmin_substring_length = len(min_substring)# 如果目标字符串的所有字符都已找到if len(remaining_target) == 0:index = temp_indexremaining_target = tfound_all_chars = Falsecurrent_substring = ''return min_substring

时间复杂度：

• 时间复杂度：$O(n)$， 其中 n 是字符串 $s$ 的长度。
  由于每个字符最多被指针 index 访问一次，因此时间复杂度为 $O(n)$。
• 空间复杂度：$O(k)$， 其中 k 是字符集 $t$ 的大小。
  需要额外的空间来存储字符串 remaining_target 和 current_substring，其大小与字符集的大小成正比。

结果

python3的代码在用例165/168处提示超时，因此我用deepseek将代码转成了C++的形式提交了。以下是C++的提交结果和代码（C++的代码我没有检查）：

#include <string>
#include <unordered_map>
#include <algorithm>class Solution {
public:std::string minWindow(std::string s, std::string t) {// 统计 t 中每个字符的出现次数std::unordered_map<char, int> t_count;for (char c : t) {t_count[c]++;}// 记录当前窗口内每个字符的出现次数std::unordered_map<char, int> window_count;int required = t_count.size(); // 需要匹配的字符种类数int formed = 0; // 当前窗口内已匹配的字符种类数int left = 0, right = 0; // 滑动窗口的左右指针int min_len = s.size() + 1; // 最小窗口的长度int min_left = 0; // 最小窗口的左指针while (right < s.size()) {// 扩展窗口char c = s[right];window_count[c]++;if (t_count.find(c) != t_count.end() && window_count[c] == t_count[c]) {formed++;}// 收缩窗口while (left <= right && formed == required) {c = s[left];if (right - left + 1 < min_len) {min_len = right - left + 1;min_left = left;}window_count[c]--;if (t_count.find(c) != t_count.end() && window_count[c] < t_count[c]) {formed--;}left++;}right++;}return min_len == s.size() + 1 ? "" : s.substr(min_left, min_len);}
};

官方解题思路

其核心思想也是使用滑动窗口的思想，结合哈希表来找到字符串 $s$ 中包含字符串 $t$ 所有字符的最小子串。

初始化：

• 使用 unordered_map ori 来记录目标字符串 t 中每个字符的出现次数。
• 定义两个指针 l 和 r，分别表示当前窗口的左边界和右边界。
• 定义变量 len 来记录当前找到的最小子串的长度，ansL 和 ansR 分别记录最小子串的起始和结束位置。

遍历字符串：

首先，右指针 r 向右移动，扩展窗口，直到窗口包含目标字符串 t 中的所有字符。每次右指针移动时，更新当前窗口中字符的计数。当窗口包含了 t 中所有字符时，尝试通过移动左指针 l 来收缩窗口，寻找更小的覆盖子串。每次收缩时，更新当前窗口中字符的计数。在每次收缩窗口时，检查当前窗口的大小是否小于之前记录的最小子串长度。如果是，则更新最小子串的起始和结束位置。遍历完成后，返回从 ansL 到 ansR 的子串。如果未找到符合条件的子串，则返回空字符串。

class Solution {
public:unordered_map <char, int> ori, cnt;bool check() {for (const auto &p: ori) {if (cnt[p.first] < p.second) {return false;}}return true;}string minWindow(string s, string t) {for (const auto &c: t) {++ori[c];}int l = 0, r = -1;int len = INT_MAX, ansL = -1, ansR = -1;while (r < int(s.size())) {if (ori.find(s[++r]) != ori.end()) {++cnt[s[r]];}while (check() && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;}if (ori.find(s[l]) != ori.end()) {--cnt[s[l]];}++l;}}return ansL == -1 ? string() : s.substr(ansL, len);}
};

时间复杂度：

• 时间复杂度：$O(n)$， 其中 n 是字符串 s 的长度。
  由于每个字符最多被指针 l 和 r 各访问一次，因此时间复杂度为 $O(n)$。
• 空间复杂度：$O(k)$， 其中 k 是字符集的大小。
  需要额外的空间来存储哈希表 ori，其大小与字符集的大小成正比。

结果

算法分析

同样的思路，我的算法要比官方题解效率更高，主要可能有以下两方面的原因：

数据结构的选择：

官方题解： 使用了 unordered_map 来记录字符的出现次数。
我的算法： 使用了更高效的数据结构，即临时变量和数组。
影响： 对于字符集大小固定的情况，使用临时变量数组可以减少哈希计算的开销，从而提高效率。

字符串操作：

官方题解： 每次收缩窗口时，会频繁地进行字符串截取操作。
我的算法：通过记录子串的起始位置和长度，避免了多次字符串截取。
影响： 减少字符串操作可以降低时间复杂度，提升性能。