LC 76. 最小覆盖子串

题目描述

这是 LeetCode 上的 76. 最小覆盖子串 ，难度为困难。

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。

如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

注意：

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

示例 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 由英文字母组成

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

滑动窗口

定义两个长度为 $60$（足够存下所有字母种类）的数组 c1 和 c2，用于存储字符频率。其中 c1 用于记录字符串 t 中字符的频率，c2 用于记录当前滑动窗口内字符的频率。

设定好字母与频率数组下标的映射关系：小写字母 a-z 对应下标 0-25，大写字母 A-Z 对应下标 26-51。

使用变量 tot 来记录还需要匹配的字符种类数，当 tot = 0 代表当前滑动窗口对应的子串能够实现对 t 的覆盖，即任意字符满足 $c2[i] \geq c1[i]$。

使用双指针 j 和 i 表示滑动窗口的左右边界。从前往后遍历字符串 s，在每个位置上更新字符频率数组 c2。若 c2 中字符的频率达到了 c1 中的字符频率，则将 tot 减 1，表示一个字符已经匹配完成。

每当右边界往后移动一步之后，滑动窗口会增加一个字符。此时我们检查左边界能否右移，同时不会使得 tot 变大。即每次右边界右移后，我们检查左边界 $c2[j] > c1[j]$ 是否满足：

若满足：说明当前左边界指向字符并非必须，当前子串 $s[j…i]$ 必然不是最短子串。我们让左边界 j 进行右移，并重复进行左边界 $c2[j] > c1[j]$ 的检查，直到窗口不能再收缩
若不满足：说明当前窗口没有任何一个后缀字符串能够实现对 t 的覆盖，我们并不能对窗口实现收缩

每次对窗口移动完成后，我们检查当前 tot 是否为 $0$（对字符串 t 的覆盖是否完成），若为 $0$ 则尝试用当前窗口对应的字符串 $s[j…i]$ 更新 ans。

Java 代码：

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), tot = 0;
        int[] c1 = new int[60], c2 = new int[60];
        for (char x : t.toCharArray()) {
            if (++c1[getIdx(x)] == 1) tot++;
        }
        String ans = "";
        for (int i = 0, j = 0; i < n; i++) {
            int idx1 = getIdx(s.charAt(i));
            if (++c2[idx1] == c1[idx1]) tot--;
            while (j < i) {
                int idx2 = getIdx(s.charAt(j));
                if (c2[idx2] > c1[idx2] && --c2[idx2] >= 0) j++;
                else break;
            }
            if (tot == 0 && (ans.length() == 0 || ans.length() > i - j + 1)) ans = s.substring(j, i + 1);
        }
        return ans;
    }
    int getIdx(char x) {
        return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';
    }
}

C++ 代码：

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.length(), tot = 0;
        vector<int> c1(60), c2(60);
        for (char x : t) {
            if (++c1[getIdx(x)] == 1) tot++;
        }
        string ans = "";
        for (int i = 0, j = 0; i < n; i++) {
            int idx1 = getIdx(s[i]);
            if (++c2[idx1] == c1[idx1]) tot--;
            while (j < i) {
                int idx2 = getIdx(s[j]);
                if (c2[idx2] > c1[idx2] && --c2[idx2] >= 0) j++;
                else break;
            }
            if (tot == 0 && (ans.empty() || ans.length() > i - j + 1)) ans = s.substr(j, i - j + 1);
        }
        return ans;
    }
    int getIdx(char x) {
        return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';
    }
};

Python 代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        def getIdx(x):
            return ord(x) - ord('A') + 26 if 'A' <= x <= 'Z' else ord(x) - ord('a')

        n, tot = len(s), 0
        c1, c2 = [0] * 60, [0] * 60
        for x in t:
            idx = getIdx(x)
            c1[idx] += 1
            if c1[idx] == 1:
                tot += 1
        ans = ""
        j = 0
        for i in range(n):
            idx1 = getIdx(s[i])
            c2[idx1] += 1
            if c2[idx1] == c1[idx1]:
                tot -= 1
            while j < i:
                idx2 = getIdx(s[j])
                if c2[idx2] > c1[idx2]:
                    j += 1
                    c2[idx2] -= 1
                else:
                    break
            if tot == 0 and (not ans or len(ans) > i - j + 1):
                ans = s[j:i + 1]
        return ans

TypeScript 代码：

function minWindow(s: string, t: string): string {
    let n = s.length, tot = 0;
    const c1 = Array(60).fill(0), c2 = Array(60).fill(0);
    for (const x of t) {
        if (++c1[getIdx(x)] === 1) tot++;
    }
    let ans = "";
    for (let i = 0, j = 0; i < n; i++) {
        const idx1 = getIdx(s[i]);
        if (++c2[idx1] == c1[idx1]) tot--;
        while (j < i) {
            const idx2 = getIdx(s[j]);
            if (c2[idx2] > c1[idx2] && --c2[idx2] >= 0) j++;
            else break;
        }
        if (tot == 0 && (!ans || ans.length > i - j + 1)) ans = s.substring(j, i + 1);
    }
    return ans;
}
function getIdx(x: string): number {
    return x >= 'A' && x <= 'Z' ? x.charCodeAt(0) - 'A'.charCodeAt(0) + 26 : x.charCodeAt(0) - 'a'.charCodeAt(0);
}

时间复杂度：$O(n + m)$
空间复杂度：$O(C)$，其中 $C = 26 \times 2$，为字符集大小

最后

这是我们「刷穿 LeetCode」系列文章的第 No.76 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

双指针滑动窗口

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 649. Dota2 参议院上一篇

LC 1657. 确定两个字符串是否接近下一篇