题目

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

注意：

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

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "a"
输出："a"

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

解答 & 代码

滑动窗口：

定义左闭右开的滑动窗口 [left, right)，初始化窗口长度为 0，即 left = 0，right = 0
寻找一个可行解：先不断增大 right 指针，使得窗口右边界扩大，直到窗口内包含的字符满足条件
优化可行解，找到最优解：然后，不断增加 left 指针，使得窗口左边界收缩，直到窗口内包含的字符不再不再满足条件
循环重复第 2、3 步，直到 right 走到字符串 s 的尽头

另外，如何判断窗口内的字符是否满足条件？

需要设置 **need** 和 **window** 两个哈希表，作为计数器，分别记录字符串 t 中出现的字符及出现的次数、窗口中的字符及出现的次数（只记录 need 包含的字符）。
设置一个 **validChCnt**，代表窗口中满足 need 条件的字符个数。每次窗口扩张，window 增加某个字符的计数，如果更新后该字符计数恰好等于 need 中该字符的计数，则更新后该字符变得满足条件， validChCnt +1；每次窗口收缩，window 减少某个字符的计数，如果更新前该字符计数恰好等于 need 中该字符的计数，则更新后该字符不再满足条件， validChCnt -1
如果 validChCnt == need.size()，则窗口内的字符满足条件

滑动窗口题目，可以直接套模板，只需要考虑 4 个问题：

当 right 指针右移，窗口右边界扩张，即加入字符时，应该更新哪些数据？

应当增加 window 对应字符的计数，如果增加计数后窗口中该字符个数 = need 中该字符需要的个数，则 validChCnt +1

什么条件下，应该暂停扩大窗口，开始 left 指针右移、收缩窗口左边界？

当满足 need 条件的字符个数 validChCnt == need 需要的字符种类数，窗口左侧开始收缩，优化可行解，寻找最优解

当 left 指针右移，窗口左边界收缩，即移出字符时，应该更新哪些数据？

应当减少 window 对应字符的计数，如果减少计数前窗口中该字符个数 = need 中该字符需要的个数，则 validChCnt -1

题目要求的结果应该在扩大窗口时更新，还是在收缩窗口时更新？

应该在收缩窗口时更新最终结果，因为求的是最优解

另外，注意：C++ 的 **unordered_map**，通过 **map[key]** 访问对应的值，如果这个 **key** 不存在，会自动创建这个 **key**，并将 **map[key]** 赋值为 0，因此无需先判断哈希表中是否存在 key，可以直接使用 ++map[key]

class Solution {
public:
    string minWindow(string s, string t) {
        // 设置两个哈希表，相当于计数器
        unordered_map<char, int> need;        // 记录字符串 t 中出现的字符及出现的次数 
        unordered_map<char, int> window;    // 记录窗口中的字符及出现的次数，只记录 need 包含的字符
        // 初始化，将 t 中出现的字符和出现的次数存入哈希表 need
        for(int i = 0; i < t.size(); ++i)
            ++need[t[i]];
        int minStart = 0;        // 最小覆盖子串的起点
        int minLen = INT_MAX;    // 最小覆盖子串的长度
        // 1. 初始化窗口长度为 0，即左、右指针设为 0，窗口是左闭右开区间 [left, right)
        int left = 0;            // 左指针（含）
        int right = 0;            // 右指针（不含）
        int validChCnt = 0;        // 代表窗口中满足 need 条件的字符个数
        // 滑动窗口
        while(right < s.size())
        {
            char c = s[right];    // 将移入窗口的字符
            // 2. right 指针右移，窗口扩大
            ++right;
            // 窗口内数据的更新：若当前字符是 need 需要的，窗口内该字符计数 +1
            // 若更新后窗口内该字符计数 == need 需要该字符的数量，则满足条件的字符个数 +1
            if(need.find(c) != need.end())
            {
                ++window[c];
                if(window[c] == need[c])
                    ++validChCnt;
            }
            // debug
            // cout << "window: [" << left << ", " << right << "]" << endl;
            // 判断窗口左侧是否要收缩，即 left 指针是否要右移
            // 当满足 need 条件的字符个数 validChCnt == need 的字符种类数，窗口左侧收缩
            while(validChCnt == need.size())
            {
                // 更新最小覆盖字串
                if(right - left < minLen)
                {
                    minStart = left;
                    minLen = right - left;
                }
                // 以下步骤和窗口右侧扩大是对称的
                char deleteC = s[left];        // 将要删除的字符
                // 3. left 指针右移，窗口收缩
                ++left;
                // 窗口内数据的更新：若当前字符是 need 需要的，窗口内该字符计数 -1
                // 若更新后窗口内该字符计数 < need 需要该字符的数量，则满足条件的字符个数 -1
                if(need.find(deleteC) != need.end())
                {
                    if(window[deleteC] == need[deleteC])
                        --validChCnt;
                    --window[deleteC];
                }
                // debug
                // cout << "window: [" << left << ", " << right << "]" << endl;
            }
        }
        return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
    }
};

复杂度分析：设字符串 s 长为 N，字符串t 包含 C 个不同的字符

时间复杂度 O(N)：最坏情况下，字符串 s 的每个字符分别被左、右指针遍历一次
空间复杂度 O(C)：两个哈希表的空间复杂度都取决于字符串t 中不同字符的种数 C

执行结果：

执行结果：通过
执行用时：12 ms, 在所有 C++ 提交中击败了 80.22% 的用户
内存消耗：7.7 MB, 在所有 C++ 提交中击败了 42.72% 的用户

hot 100

[困难] 76. 最小覆盖子串

题目

解答 & 代码