LeetCode12 - 最小覆盖子串 | 很多时候不懂事

📝 题目描述

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

测试用例保证答案唯一。
子串：子字符串是字符串中连续的非空字符序列。

示例：


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

提示：

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

💡 解题思路

方法一：滑动窗口

这个题目的思路有点类似于“LeetCode8 - 无重复字符的最长子串”，都是滑动窗口的标准写法：

“右指针主动走，左指针被动收缩”。

这道题也不例外，我们先规划两个128长度的数组（ASCII 共128个字符），用于存储 s的子串和 t 的每个字母的出现次数，并提前写好一个 check 函数用于判断 s的子串是否包含了 t 中的所有字符。

接下来就是滑动窗口法来不断迭代：

首先，right右移，将 s[right] 包含进子串中；
接下来进行检查，看 s的子串是否包含了 t 中的所有字符：
- 是，则检查子串是否更短，更短则更新答案记录，然后收缩 left 边界；重复此流程，直到 s的子串不再包含 t 中的所有字符；
- 否，则不进行操作，继续等待 right 右移。

这样，循环结束时，检查记录即可得到最终答案。

方法二：优化的滑动窗口

上面思路的主要待优化点在于判断逻辑，我们可以参照“LeetCode9 - 找到字符串中所有字母异位词”的方法，只关注目前变化的字符，并计算 needCount 是否为 0 来判断子串是否已包含 t 中所有的字符。

具体来说，我们先初始化 needCount = t.size()，也就是说，我们的 有用字符总需求量 是 needCount。接下来初始化数组 vector<int> need(128, 0)，表示 t 中 每个字符的需求量。

接下来进入滑动窗口循环：

首先，我们判断 need[s[right]] > 0 是否为真，这一步帮助我们判断目前的 s[right] 是否是我们需要的字符，是则 needCount--，然后无论是不是我们需要的字符，都要 need[s[right]]--。（这一步主要是为了进行“记账”，如果只对需要的字符进行 need[s[right]]--，那么当后续左指针移动时，所有的 need 都为 0，无法判断哪个是我们需要的）
接下来进行检查，看 needCount 是否为 0：
- 是，则检查子串是否更短，更短则更新答案记录，并判断 need[s[left]] == 0 是否为真，是则 needCount++，然后无论是不是我们需要的字符，都要 need[s[left]]++，然后收缩 left 边界；重复此流程，直到 ``needCount不再为0`；
- 否，则不进行操作，继续等待 right 右移。

接下来解释一下上面说的“记账”思路，随着窗口的滑动，need[c] 的值会产生三种状态：

大于 0 (> 0)：表示当前窗口还需要多少个字符 c 才能满足 t 的要求。
等于 0 (== 0)：表示当前窗口内字符 c 的数量刚好满足 t 的要求（或者本来就不需要，且窗口里也没有）。
小于 0 (< 0)：表示当前窗口内字符 c 的数量超标了（即冗余字符）。这包含两种情况：
- 这个字符根本不在 t 中，但被我们圈进了窗口里。
- 这个字符在 t 中，但窗口里包含该字符的数量多于 t 中要求的数量。

也就是说，我们可以利用 need 数组，来记录子串中的字符状态，从而节省了“子串是否包含 t 中所有字符”的判断开销。

🔧 代码实现

1、滑动窗口

class Solution {
public:
    bool check(vector<int>& mCount, vector<int>& nCount){
        for(int i = 0; i < 128; i++){
            if(mCount[i] - nCount[i] < 0){
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        int m = s.size(), n = t.size(), left = 0, right = 0, ansLeft = 0, ansRight = 0, ansLength = INT_MAX;
        if (m < n) return "";
        vector<int> mCount(128, 0), nCount(128, 0);
        for (char c : t) {
            nCount[c]++;
        }
        for(right = 0; right < m; right++) {
            mCount[s[right]]++;
            while(check(mCount, nCount)){
                if((right - left + 1) <= ansLength){
                    ansLeft = left;
                    ansRight = right;
                    ansLength = right - left + 1;
                }
                mCount[s[left]]--;
                left++;
            }
        }
        return ansLength == INT_MAX ? "" : s.substr(ansLeft, ansLength);
    }
};

2、优化的滑动窗口

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.size(), n = t.size(), left = 0, right = 0, ansLeft = 0, ansLength = INT_MAX;
        vector<int> need(128, 0);
        int needCount = n;
        for(char c : t){
            need[c]++;
        }
        for(right = 0; right < m; right++){
            // 大于零说明需要
            if(need[s[right]] > 0){
                needCount--;
            }
            // 无论是不是需要，都无脑--，当账本使用
            need[s[right]]--;
            // 满足条件，开始收缩左边界
            while(needCount == 0){
                // 更新答案
                if (right - left + 1 < ansLength){
                    ansLeft = left;
                    ansLength = right - left + 1;
                }
                // 开始收缩
                if(need[s[left]] == 0){
                    needCount++;
                }
                // 无论是不是需要，都无脑++，当账本使用
                need[s[left]]++;
                left++;
            }
        }
        return ansLength == INT_MAX ? "" : s.substr(ansLeft, ansLength);
    }
};

📊 复杂度分析

1、滑动窗口

时间复杂度： $O(Σ×m+n)$ ，此处 $Σ=128$ ，每次需要判断子串是否包含了所有的 t 中的字符。
空间复杂度： $O(Σ)=O(1)$ ，额外需要两个 $128$ 的数组，不随输入规模变化。

2、优化的滑动窗口

时间复杂度： $O(m+n)$ ，判断子串时，不每次都去全局检查 128 个字符，而是只关注 needCount，节省了时间开销。
空间复杂度： $O(Σ)=O(1)$ ，额外需要一个 $128$ 的数组，不随输入规模变化。

🎯 总结

核心思想：熟悉滑动窗口的公式写法，及时想起来滑动窗口。