分析

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

其实就是可以包含其他字母的最短异位词。

---

题解

滑动窗口+计数

我们可以沿用异位词的思想：

异位词（438题）：窗口字符计数 $== t$ 计数 最小覆盖子串（76题）：窗口字符计数 $\ge t$ 计数

滑动窗口：右指针不断扩大窗口，一旦窗口[l, r]满足覆盖 t 全部字符，就不断收缩左指针，记录最小合法窗口。

check()：遍历字母，判断当前窗口字符计数是否满足t的需求。

代码

// 判断窗口是否满足覆盖t
bool check(const vector<int>& sCount,const vector<int>& tCount){
    for(int i = 0; i < 128; i++){
        if(tCount[i] > 0 && sCount[i] < tCount[i]){
            return false;
        }
    }
    return true;
}
class Solution {
public:
    string minWindow(string s, string t) {
        int sLen = s.size();
        int tLen = t.size();
        if(sLen < tLen) return "";
        vector<int> sCount(128,0);
        vector<int> tCount(128,0);
        for(char ch : t) {
            tCount[ch]++;
        }
        int l = 0;
        int start = 0;
        int minLen = INT_MAX;
        for(int r = 0; r < sLen; r++) {
            sCount[s[r]]++;
            while(check(sCount,tCount)){
                int cur = r - l + 1;
                if(cur < minLen){
                    minLen = cur;
                    start = l;
                }
                sCount[s[l]]--;
                l++;
            }
        }
        if(minLen == INT_MAX) return "";
        return s.substr(start,minLen);
    }
};

时间复杂度：$O(128 \cdot n)$，n是s长度。

外层 r 循环 n 次；每一次进入while会调用check()循环 128 次；左右指针总共最多移动2n次。128 是常数，平均可以看作 $O(n)$。

空间复杂度：$O(1)$，固定大小 128 数组，和输入规模无关。

优化版滑动窗口

维护 valid 变量，记录满足数量要求的字符种类，不需要每次遍历 128 数组。

• valid：t 中一共有多少种需要的字符
• match：当前窗口里，已经满足数量要求的字符种类
• 当 match == valid：窗口完全覆盖 t，进入收缩阶段

代码

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> sCount(128,0), tCount(128,0);
        for(char c : t) tCount[c]++;
        int valid = 0; //满足条件的字符种类
        for(int i = 0; i < 128; i++){
            if(tCount[i]>0) valid++;
        }
        int l = 0, start = 0, minLen = INT_MAX;
        int match = 0; //当前窗口匹配成功的种类
        for(int r=0;r<s.size();r++){
            char c = s[r];
            sCount[c]++;
            if(tCount[c] && sCount[c] == tCount[c]){
                match++;
            }
            while(match == valid){
                int cur = r - l + 1;
                if(cur < minLen){
                    minLen = cur;
                    start = l;
                }
                char out = s[l];
                if(tCount[out] && sCount[out] == tCount[out]){
                    match--;
                }
                sCount[out]--;
                l++;
            }
        }
        return minLen == INT_MAX ? "" : s.substr(start,minLen);
    }
};

时间复杂度：$O(n+m)$，n=s 长度，m=t 长度。左右指针各走一遍 s，无内层循环。 空间复杂度：$O(1)$，固定 128 大小数组，常数空间。

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