LeetCode76. [H]最小覆盖子串（滑动窗口）

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

一、思路

本题的关键在于什么叫做覆盖​？

对于给定的字符串t，s的子串中每个字母的出现次数都​​大于等于​​字符串t中该字母的出现次数，那么该子串就覆盖了字符串s

事实上本题可以说是438. 找到字符串中所有字母异位词 - 力扣（LeetCode）的变体，对于找到字母异位词，我们需要保证s的子串中每一个字符的出现都等于t中的出现次数，而对于本题，只需要大于等于即可（等于的情况其实就代表s的字串是t的异位词）。

二、解题方法

2.1 滑动窗口+统计

1. 使用一个数组tCount，统计字符串t中每一个字母的出现次数
2. 滑动窗口，每当右端点新滑入一个字符，就将sCount[s[r]]++

3. 之后判断字串s中每个字母的出现次数是否大于等于t中该字母的出现次数

   • 如果此时窗口的长度小于记录的结果，则记录新结果
   • 如果窗口长度大于记录的结果，滑出左端点， 再次检查，直到找到新的答案，或者窗口中的子串不再覆盖字符串s

2.1.1 代码

class Solution
{
public:
    //检查字串中每个字符的出现次数是否大于等于t中每个字符的出现次数
    bool check(int scount[], int tcount[])
    {
        for (int i = 'A'; i <= 'Z'; i++)
        {
            if (scount[i] < tcount[i])
            {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++)
        {
            if (scount[i] < tcount[i])
            {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t)
    {
        //a-z：对应 97-122
        //A-Z：对应 65-90
        int scount[128];
        int tcount[128];
        int n = s.size();
        //统计t中每个字符的出现次数
        for (auto c : t)
        {
            tcount[c]++;
        }
        //ans：左右边界
        int ansl = -1, ansr = n;
        //初始化左端点
        int l=0;
        //滑入右端点
        for (int r =  0; r < n; r++)
        {
            //增加窗口中字符计数
            scount[s[r]]++;
            //当s中所有字母出现次数大于等于t中
            while(check(scount,tcount))
            {
                //如果当前s就是更小的字串，记录新结果
                if(r-l<ansr-ansl)
                {
                    ansr=r;
                    ansl=l;
                }
                //滑出左端点，直到找到更短的字串/不满足s中所有字母出现次数大于等于t中
                else
                {
                    scount[s[l]]--;
                    l++;
                }
            }
        }
        return ansl>=0 ? s.substr(ansl,ansr-ansl+1) : "";
    }
};

2.1.2 复杂度分析

• 时间复杂度：O(∣Σ∣m+n)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。注意 left 只会增加不会减少，left 每增加一次，我们就花费 O(∣Σ∣) 的时间。因为 left 至多增加 m 次，所以二重循环的时间复杂度为 O(∣Σ∣m)，再算上统计 t 字母出现次数的时间 O(n)，总的时间复杂度为 O(∣Σ∣m+n)。
• 空间复杂度：O(∣Σ∣)。如果创建了大小为 128 的数组，则 ∣Σ∣=128。

2.2 优化

在2.1的解法中，我们每次都需要花费 O(∣Σ∣) 的时间去判断s的字串是否覆盖t，其实我们可以引入一个新的变量，用一个变量 维护目前子串中有 less 种字母的出现次数小于 t 中字母的出现次数

2.2.1 代码

class Solution
{
public:
    // 优化
    string minWindow(string s, string t)
    {
        int n=s.size();
        //less用于统计当前字串中还有多少种字母出现次数小于t中的出现次数
        int ansl=-1,ansr=n,less=0,l=0;
        int cnt[128] {};
        for(char c : t)
        {
            
            if(cnt[c]==0) less++;
            cnt[c]++;
            
        }

        for(int r=0;r<n;r++)
        {
            
            char rc=s[r];
            cnt[rc]--;
            //证明窗口内该字符出现次数等于t中的出现次数
            if(cnt[rc]==0)
            {
                //减少less
                less--;
            }
            //当less=0的时候代表s的子串所有字母的出现次数都大于等于t中所有字母的出现次数
            while(less==0)
            {   
                if(r-l<ansr-ansl)
                {
                    ansr=r;
                    ansl=l;
                }
                //尝试寻找更短的子串
                char lc=s[l];
                
                if(cnt[lc]==0)
                {
                    less++;
                }
                cnt[lc]++;
                l++;
            }
        }
        return ansl<0 ? "": s.substr(ansl,ansr-ansl+1);
    }
};

2.2.2 复杂度分析

• 时间复杂度：O(m+n) 或 O(m+n+∣Σ∣)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣=128。注意 left 只会增加不会减少，二重循环的时间复杂度为 O(m)。使用哈希表写法的时间复杂度为 O(m+n)，数组写法的时间复杂度为 O(m+n+∣Σ∣)。
• 空间复杂度：O(∣Σ∣)。无论 m 和 n 有多大，额外空间都不会超过 O(∣Σ∣)。

‍

三、参考

76. 最小覆盖子串 （灵茶山艾府）

‍

这篇文章介绍了LeetCode第76题「最小覆盖子串」的滑动窗口解法。关键思路是：子串需要覆盖目标字符串t，即子串中每个字符的出现次数都大于等于t中的对应次数。文章提供了两种解法：1) 基础滑动窗口法，使用数组统计字符出现次数并检查是否满足条件，时间复杂度O(52m+n)；2) 优化解法，引入less变量实时跟踪不满足条件的字符种类数，减少不必要的检查。两种方法都通过移动窗口边界来寻找最短覆盖子串，优化解法通过维护状态变量提升了效率。