【哈希表, 滑动窗口】最小覆盖子串

题目

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

注意：

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

示例 1：

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

示例 2：

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

示例 3:

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

提示：

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

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

解题

方法一：滑动窗口哈希表

思路

本题使用滑动窗口可解，具体做法：

首先定义左右指针(left、right)并初始化为 $0$ ，它们标识了一个范围为 $[left, right)$ 的滑动窗口，再维护一个哈希表(window)用于记录滑动窗口中每个字符出现的次数。
我们先不断地增加 right 指针以扩大窗口，直到窗口中的所有字符符合要求（包含了 t 中的所有字符）。
此时停止增加 right，转而不断增加 left 指针以缩小窗口，此时窗口每次小都不断更新结果，直到窗口首次不符合要求（不包含 t 中的某些字符了）时停止减小，进行下一次循环。
重复第 2 步与第 3 步，直到 right 到达字符串 s 的末尾。

参考：我写了首诗，把滑动窗口算法算法变成了默写题 - 最小覆盖子串

代码

class Solution {
    public String minWindow(String s, String t) {
        // require记录t中所有字符的出现次数    window维护窗口中字符的出现次数
        Map<Character, Integer> require = new HashMap<>(), window = new HashMap<>();
        for (char ch : t.toCharArray()) require.put(ch, require.getOrDefault(ch, 0) + 1);
        char[] chs = s.toCharArray();
        int n = chs.length;
        // 左右指针标识一个窗口
        int left = 0, right = 0;
        // 最小子串的开头和长度
        // 长度初始化为一个比较大的值 如果没被更新就说明无解
        int minBegin = 0, minEnd = n + 1;
        outer: while (right < n) {
            // 拿到当前字符 并把右指针增加
            char curr = chs[right++];
            // 滑动窗口增大
            window.put(curr, window.getOrDefault(curr, 0) + 1);
            for (Map.Entry<Character, Integer> entry : require.entrySet()) {
                // 遍历并对比 如果require是window的子集就说明窗口现在符合要求
                // 否则不符合要求 直接去下一个循环增大窗口
                if (window.getOrDefault(entry.getKey(), 0) < entry.getValue()) continue outer;
            }
            // 只有窗口符合要求才会走到这
            // 更新最小子串
            if (right - left < minEnd - minBegin) {
                minBegin = left;
                minEnd = right;
            }
            while (true) {
                // 拿到当前字符 并把左指针增加
                curr = chs[left++];
                // 滑动窗口缩小
                window.put(curr, window.get(curr) - 1);
                // 如果窗口缩小时首次使窗口不符合要求的话就不再缩小进入下一次循环
                if (require.containsKey(curr) && window.get(curr) < require.get(curr)) break;
                // 否则不断更新最小子串
                else if (right - left < minEnd - minBegin) {
                    minBegin = left;
                    minEnd = right;
                }
            }
        }
        // 如果最小子串长度没被更新就说明无解返回空串 否则返回对应子串
        return minEnd == n + 1 ? "" : s.substring(minBegin, minEnd);
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> require, window;
        for (char& ch : t) ++require[ch];
        int left = 0, right = 0;
        int n = s.length();
        int min_begin = 0, min_len = numeric_limits<int>::max();
        while (right < n) {
            ++window[s[right++]];
            for (auto& pr : require) {
                if (window[pr.first] < pr.second) goto out;
            }
            if (right - left < min_len) {
                min_begin = left;
                min_len = right - left;
            }
            while (true) {
                char curr = s[left++];
                if (--window[curr] < require[curr]) break;
                else if (right - left < min_len) {
                    min_begin = left;
                    min_len = right - left;
                }
            }
            out:;
        }
        return min_len > n ? "" : s.substr(min_begin, min_len);
    }
};

由于字符串中只包含英文字母，可以用数组代替哈希表显著提升效率。

class Solution {
    static final int HASH_LEN = 'z' + 1;

    public String minWindow(String s, String t) {
        int[] require = new int[HASH_LEN], window = new int[HASH_LEN];
        // target表示字符串t中不为0的字符有几个
        int target = 0;
        for (char ch : t.toCharArray()) {
            if (++require[ch] == 1) ++target;
        }
        char[] chs = s.toCharArray();
        int n = chs.length;
        // valid表示窗口中与t中数量相同的字符的个数
        // 这样如果valid与target相等就说明窗口符合要求
        int left = 0, right = 0, valid = 0;
        int minBegin = 0, minEnd = Integer.MAX_VALUE;
        while (right < n) {
            char curr = chs[right++];
            // 每次增加字符时额外判断一下变动的是否是“关键字符” 如果是就把valid增加
            // “关键字符”是指该字符的变动会导致窗口的状态变为有效/无效
            if (++window[curr] == require[curr]) ++valid;
            while (valid == target) {
                if (right - left < minEnd - minBegin) {
                    minBegin = left;
                    minEnd = right;
                }
                curr = chs[left++];
                // 删除字符时也要额外判断“关键字符”
                if (window[curr]-- == require[curr]) --valid;
            }
        }
        return minEnd > n ? "" : s.substring(minBegin, minEnd);
    }
}

这里使用了一种巧妙的方法来判断窗口是否符合要求，不用每次判断都遍历一次窗口了。

#define HASH_LEN 'z' + 1

class Solution {
public:
    string minWindow(string s, string t) {
        int require[HASH_LEN] = {0}, window[HASH_LEN] = {0};
        int target = 0;
        for (char& ch : t) {
            if (++require[ch] == 1) ++target;  
        }
        int left = 0, right = 0, valid = 0;
        int n = s.length();
        int min_begin = 0, min_len = numeric_limits<int>::max();
        while (right < n) {
            char curr = s[right++];
            if (++window[curr] == require[curr]) ++valid;
            while (valid == target) {
                if (right - left < min_len) {
                    min_begin = left;
                    min_len = right - left;
                }
                curr = s[left++];
                if (window[curr]-- == require[curr]) --valid;
            }
        }
        return min_len > n ? "" : s.substr(min_begin, min_len);
    }
};

目录CONTENT

【哈希表, 滑动窗口】最小覆盖子串

题目

解题

方法一：滑动窗口哈希表

思路

代码

评论区

【哈希表, 滑动窗口】最小覆盖子串

题目

解题

方法一：滑动窗口 哈希表

思路

代码

评论区

方法一：滑动窗口哈希表