76. 最小覆盖子串¶

力扣链接(困难)：https://leetcode.cn/problems/minimum-window-substring

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

注意：

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

示例 1：

Text Only
1 2 3	`输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。`

示例 2：

Text Only
1 2 3	`输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。`

示例 3:

Text Only
1 2 3 4	`输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。`

提示：

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

个人题解¶

初版¶

C++
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<int, int>cnt, subCnt;
        int i = 0, j = 0;
        string res;
        if(s.size() < t.size())
            return "";
        //处理t
        for(auto it : t) {
            cnt[it]++;
        }
        int checked = 0;
        //处理s
        for(; j < s.size(); j++) {
            if(cnt.count(s[j])){
                //过滤变态数据
                if(subCnt[s[j]] - cnt[s[j]] > 10 && s[j] == s[i]) {
                    i++;
                    continue;
                }

                subCnt[s[j]]++;
                if(subCnt[s[j]] == cnt[s[j]]) {
                    checked++;
                }
            }
            //缩小窗口(当已经满足子串要求时)
            //有两种情况可以缩小，第一种是该字符不存在于t串，第二种是该字符数量>t串中的数量

            //左边界
            while(subCnt.size() == cnt.size() && checked == cnt.size()) {
                int len = j - i + 1;
                res = (res.size() > 0 && res.size() < s.substr(i, len).size()) ? res : s.substr(i, len);
                if(cnt.count(s[i]) && subCnt[s[i]] > cnt[s[i]]) {
                    subCnt[s[i]]--;
                    i++;
                } else if(!cnt.count(s[i])) {
                    i++;
                } else
                    break;  //注意一定要break
            }
        }
        //右边界
        while(subCnt.size() == cnt.size() && checked == cnt.size()) {
            int len = j - i + 1;
            res = (res.size() > 0 && res.size() < s.substr(i, len).size()) ? res : s.substr(i, len);
            if(cnt.count(s[j]) && subCnt[s[j]] > cnt[s[j]]) {
                subCnt[s[j]]--;
                j--;
            } else if(!cnt.count(s[j])) {
                j--;
            } else
                break;  //注意一定要break
        }
        return res;
    }
};

改版¶

C++
class Solution {
public:
    //记录字符频数
    unordered_map <char, int> ori, cnt;

    //检查s串中的字符频数是否满足题目要求
    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        //处理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())) {
            //如果s串中当前字符存在于t串，则记录至哈希
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            //check()检查当前滑动窗口子串是否满足要求
            while (check() && l <= r) {
                //仅记录长度较小的串
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                //如果左字符存在于t中才在哈希中处理
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }
        //ansL没有更新就代表没找到子串
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

官方题解¶

滑动窗口¶

思路和算法

本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。

考虑如何优化？如果 \(s=XX⋯XABCXXXX\)，\(t=ABC\)，那么显然 \([XX⋯XABC]\) 是第一个得到的「可行」区间，得到这个可行区间后，我们按照「收缩」窗口的原则更新左边界，得到最小区间。我们其实做了一些无用的操作，就是更新右边界的时候「延伸」进了很多无用的 X，更新左边界的时候「收缩」扔掉了这些无用的 X，做了这么多无用的操作，只是为了得到短短的 ABC。没错，其实在 s 中，有的字符我们是不关心的，我们只关心 t 中出现的字符，我们可不可以先预处理 s，扔掉那些 t 中没有出现的字符，然后再做滑动窗口呢？也许你会说，这样可能出现 \(XXABXXC\) 的情况，在统计长度的时候可以扔掉前两个 X，但是不扔掉中间的 X，怎样解决这个问题呢？优化后的时空复杂度又是多少？这里代码给出没有优化的版本，以上的三个问题留给读者思考，欢迎大家在评论区给出答案哟。

C++
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);
    }
};

复杂度分析¶

时间复杂度：最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为 \(O(C⋅∣s∣+∣t∣)\)。
空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为 \(O(C)\)。