滑动窗口算法详解：如何求解最小覆盖子串问题

滑动窗口算法详解：如何求解最小覆盖子串问题

引用

CSDN

1.

https://m.blog.csdn.net/xsc2004zyj/article/details/144992191

在字符串处理和算法面试中，"最小覆盖子串"是一个经典问题。本文将详细讲解如何使用滑动窗口算法解决这个问题，包括算法原理、优化思路以及完整的代码实现。

一.题目描述

76. 最小覆盖子串 - 力扣（LeetCode）
    

二.题目解析

题目要求在字符串s中找到一个子串，该子串包含字符串t的所有字符，并返回最短的子串。如果s中不包含这样的子串，则返回一个空串。

需要注意的是：

• 如果字符串t包含重复字符（如"aaac"），那么在s中寻找子串时必须包含所有字符，不能只出现一次。
• 子串中的字符顺序可以任意，只要包含t中的所有字符即可。

三.算法原理

1.暴力解法

暴力解法的基本思路是枚举所有可能的子串，使用哈希表统计每个子串的字符，当子串包含t的所有字符时，记录其起始位置和长度。最后返回最短的符合条件的子串。

时间复杂度： O(N^2)，因为需要反复遍历s。
空间复杂度： O(1)，虽然使用了哈希表，但存储的都是字母，空间是常数级的。

2.滑动窗口

可以对暴力枚举进行优化，采用滑动窗口算法：

• 进窗口： right位置的元素放入哈希表中
• 判断： 如果子串满足要求，就更新结果，然后让left位置的元素出窗口
• 时间复杂度： O(N+t)，left和right最多各遍历一次s，判断时需要遍历哈希表
• 空间复杂度： O(1)，字符集只有52个字母

3.滑动窗口优化

通过引入count计数器来优化判断逻辑：

• 入窗口时： 如果该元素在两个哈希表的个数相等，说明这个字符已经满足t中该字符的出现要求，count++
• 出窗口前： 如果两个哈希表中该字符个数相等，说明该字符是有效字符，出去后count--
• 判断逻辑： count统计有效字符的种类，与t的哈希表大小进行比较

四.代码实现

在进行滑动窗口之前，需要记录t的哈希表大小，因为在滑动窗口过程中，哈希表会插入元素导致大小变化。同时，需要记录子串的起始位置和长度。

string ret;
int n = s.size();
int m = t.size();
if (n < m)
    return ret;
unordered_map<char, int> mp_t; // 统计t字符串中字符的出现次数
unordered_map<char, int> mp_s; // 统计窗口中字符的出现次数
for (auto e : t) mp_t[e]++;
int judge = mp_t.size();
int len = 0, beg = 0;
for (int l = 0, r = 0, count = 0; r < n; ++r) // count标记有效字符的种类
{
    // 进窗口 + 维护count
    mp_s[s[r]]++;
    if (mp_s[s[r]] == mp_t[s[r]]) count++;
    // 判断
    while (count == judge)
    {
        // 更新结果
        int prev = len;
        len = len == 0 ? (r - l + 1) : min(len, r - l + 1);
        if (len != prev) beg = l;
        // 出窗口
        if (mp_s[s[l]] == mp_t[s[l]]) count--;
        mp_s[s[l++]]--;
    }
}
return s.substr(beg, len);