题目链接 · 灵神原题解（署名来源）

前置知识：滑动窗口

如果您不知道滑动窗口，推荐先看视频 滑动窗口【基础算法精讲 03】，并完成 209. 长度最小的子数组 作为本题的铺垫，因为这两题都属于「越长越合法」滑动窗口。

什么是「涵盖」

看示例 1，$s$ 的子串 $\mathtt{\text{BANC}}$ 中每个字母的出现次数，都大于等于 $t=\mathtt{\text{ABC}}$ 中每个字母的出现次数，这就叫涵盖。

滑动窗口怎么滑

原理和 209 题一样，按照视频中的做法，我们枚举 $s$ 子串的右端点 $\mathit{\text{right}}$（子串最后一个字母的下标），如果子串涵盖 $t$，就不断右移左端点 $\mathit{\text{left}}$ 直到不涵盖为止。在移动过程中更新最短子串的左右端点。

具体来说：

1. 初始化 $\mathit{\text{ansLeft}}=-1,\mathit{\text{ansRight}}=m$，用来记录最短子串的左右端点，其中 $m$ 是 $s$ 的长度。
2. 用一个哈希表（或者数组）$\mathit{\text{cntT}}$ 统计 $t$ 中每个字母的出现次数。
3. 初始化 $\mathit{\text{left}}=0$，以及一个空哈希表（或者数组）$\mathit{\text{cntS}}$，用来统计 $s$ 子串中每个字母的出现次数。
4. 遍历 $s$，设当前枚举的子串右端点为 $\mathit{\text{right}}$，把 $s[\mathit{\text{right}}]$ 的出现次数加一。
5. 遍历 $\mathit{\text{cntS}}$ 中的每个字母及其出现次数，如果出现次数都大于等于 $\mathit{\text{cntT}}$ 中的字母出现次数：
   1. 如果 $\mathit{\text{right}}-\mathit{\text{left}}<\mathit{\text{ansRight}}-\mathit{\text{ansLeft}}$，说明我们找到了更短的子串，更新 $\mathit{\text{ansLeft}}=\mathit{\text{left}},\mathit{\text{ansRight}}=\mathit{\text{right}}$。
   2. 把 $s[\mathit{\text{left}}]$ 的出现次数减一。
   3. 左端点右移，即 $\mathit{\text{left}}$ 加一。
   4. 重复上述三步，直到 $\mathit{\text{cntS}}$ 有字母的出现次数小于 $\mathit{\text{cntT}}$ 中该字母的出现次数为止。
6. 最后，如果 $\mathit{\text{ansLeft}}<0$，说明没有找到符合要求的子串，返回空字符串，否则返回下标 $\mathit{\text{ansLeft}}$ 到下标 $\mathit{\text{ansRight}}$ 之间的子串。

由于本题大写字母和小写字母都有，为了方便，代码实现时可以直接创建大小为 $128$ 的数组，直接把 ASCII 值作为数组的下标。

优化前

Python 解法1

# 请选择 Python3 提交代码，而不是 Python
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt_s = Counter()  # s 子串字母的出现次数
        cnt_t = Counter(t)  # t 中字母的出现次数

        ans_left, ans_right = -1, len(s)
        left = 0

        for right, c in enumerate(s):  # 移动子串右端点
            cnt_s[c] += 1  # 右端点字母移入子串
            while cnt_s >= cnt_t:  # 涵盖
                if right - left < ans_right - ans_left:  # 找到更短的子串
                    ans_left, ans_right = left, right  # 记录此时的左右端点
                cnt_s[s[left]] -= 1  # 左端点字母移出子串
                left += 1

        return "" if ans_left < 0 else s[ans_left: ans_right + 1]

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    bool is_covered(int cnt_s[], int cnt_t[]) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cnt_s[i] < cnt_t[i]) {
                return false;
            }
        }
        return true;
    }

public:
    string minWindow(string s, string t) {
        int cnt_s[128]{}; // s 子串字母的出现次数
        int cnt_t[128]{}; // t 中字母的出现次数
        for (char c : t) {
            cnt_t[c]++;
        }

        int m = s.size();
        int ans_left = -1, ans_right = m;
        int left = 0;

        for (int right = 0; right < m; right++) { // 移动子串右端点
            cnt_s[s[right]]++; // 右端点字母移入子串
            while (is_covered(cnt_s, cnt_t)) { // 涵盖
                if (right - left < ans_right - ans_left) { // 找到更短的子串
                    ans_left = left; // 记录此时的左右端点
                    ans_right = right;
                }
                cnt_s[s[left]]--; // 左端点字母移出子串
                left++;
            }
        }

        return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left + 1);
    }
};

复杂度分析

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

优化

上面的代码每次都要花费 $\mathcal{O}(|\mathrm{\Sigma }|)$ 的时间去判断是否涵盖，能不能优化到 $\mathcal{O}(1)$ 呢？

可以。用一个变量 $\mathit{\text{geCnt}}$ 维护目前子串（窗口）中有 $\mathit{\text{geCnt}}$ 种字母的出现次数大于等于 $t$ 中相应字母的出现次数。

设 $t$ 有 $\mathit{\text{kinds}}$ 个不同的字母，那么「子串每种字母的出现次数都大于等于 $t$ 中相应字母的出现次数」等价于 $\mathit{\text{geCnt}}=\mathit{\text{kinds}}$。

如何维护 $\mathit{\text{geCnt}}$ 呢？

为了方便实现，把 $\mathit{\text{cntS}}$ 和 $\mathit{\text{cntT}}$ 合并成一个 $\mathit{\text{diff}}$，定义 $\mathit{\text{diff}}[x]=\mathit{\text{cntS}}[x]-\mathit{\text{cntT}}[x]$。如果 $\mathit{\text{diff}}[x]=0$，就意味着窗口内字母 $x$ 的出现次数和 $t$ 的一样多。

• 如果字母 $x$ 进入窗口后，$\mathit{\text{diff}}[x]=0$，这意味着 $x$ 在子串和 $t$ 中的出现次数从 $<$ 变成了 $\ge$，那么把 $\mathit{\text{geCnt}}$ 增加一。
• 如果字母 $x$ 离开窗口前，$\mathit{\text{diff}}[x]=0$，这意味着 $x$ 离开窗口后，$x$ 在子串和 $t$ 中的出现次数从 $\ge$ 变成了 $<$，那么把 $\mathit{\text{geCnt}}$ 减少一。

⚠注意：不能在 $\mathit{\text{diff}}[x]\ge 0$ 的时候就把 $\mathit{\text{geCnt}}$ 增加一。这样写的话，对于同一个字母 $x$，$\mathit{\text{diff}}[x]$ 等于 $0,1,2,\dots$ 的时候都会让 $\mathit{\text{geCnt}}$ 增加一，这就重复统计了。

Python 解法3

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 注：defaultdict 比 Counter 快
        diff = defaultdict(int)  # 窗口每种字母个数 - t 每种字母个数
        for c in t:
            diff[c] -= 1
        kinds = len(diff)  # t 中有 kinds 种不同的字母

        ans_left, ans_right = -1, len(s)
        ge_cnt = 0  # 窗口内有 ge_cnt 种字母的出现次数 >= t 中相应字母的出现次数
        left = 0

        for right, c in enumerate(s):  # 移动子串右端点
            diff[c] += 1  # 右端点字母移入子串
            if diff[c] == 0:  # 原来窗口内 c 的出现次数比 t 的少，现在一样多
                ge_cnt += 1  # 从 < 变成 >=

            while ge_cnt == kinds:  # 涵盖：所有字母的出现次数都是 >=
                if right - left < ans_right - ans_left:  # 找到更短的子串
                    ans_left, ans_right = left, right  # 记录此时的左右端点

                x = s[left]  # 左端点字母
                if diff[x] == 0:
                    # x 移出窗口之前，检查出现次数，
                    # 如果窗口内 x 的出现次数和 t 一样，
                    # 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                    ge_cnt -= 1  # 从 >= 变成 <
                diff[x] -= 1  # 左端点字母移出子串
                left += 1

        return "" if ans_left < 0 else s[ans_left: ans_right + 1]

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    string minWindow(string s, string t) {
        int diff[128]{}; // 窗口每种字母个数 - t 每种字母个数
        int kinds = 0;
        for (char c : t) {
            if (diff[c] == 0) {
                kinds++; // 统计 t 有多少个不同的字母
            }
            diff[c]--;
        }

        int m = s.size();
        int ans_left = -1, ans_right = m;
        int ge_cnt = 0; // 窗口内有 ge_cnt 种字母的出现次数 >= t 中相应字母的出现次数
        int left = 0;

        for (int right = 0; right < m; right++) { // 移动子串右端点
            char c = s[right]; // 右端点字母
            diff[c]++; // 右端点字母移入子串
            if (diff[c] == 0) { // 原来窗口内 c 的出现次数比 t 的少，现在一样多
                ge_cnt++; // 从 < 变成 >=
            }

            while (ge_cnt == kinds) { // 涵盖：所有字母的出现次数都是 >=
                if (right - left < ans_right - ans_left) { // 找到更短的子串
                    ans_left = left; // 记录此时的左右端点
                    ans_right = right;
                }

                char x = s[left]; // 左端点字母
                if (diff[x] == 0) {
                    // x 移出窗口之前，检查出现次数，
                    // 如果窗口内 x 的出现次数和 t 一样，
                    // 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                    ge_cnt--; // 从 >= 变成 <
                }
                diff[x]--; // 左端点字母移出子串
                left++;
            }
        }

        return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left + 1);
    }
};

复杂度分析

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

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府