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 <= 105
• s 和 t 由英文字母组成

解答

1. 滑动窗口

一个常见的解决方案是使用双指针法和滑动窗口技巧，并利用一个哈希表来维护字符串 t 中字符的出现次数。

我们用两个指针分别指向当前枚举的子串的左端点和右端点，同时用一个计数器维护当前子串是否已经包含了字符串 t 中的所有字符。

每当右指针移动到一个字符时，如果该字符在字符串 t 中出现过，则将哈希表中该字符的计数器减一，同时如果该字符的计数器减一后不再为 0，则将计数器减一，表示该字符已经被包含在当前子串中了。

当计数器变成 0 时，说明当前子串已经包含了字符串 t 中的所有字符，此时开始移动左指针，直到该子串不再包含字符串 t 中的所有字符，此时计数器再次变成非 0 的值，表示当前子串不再完整包含字符串 t。

在整个过程中，每当移动左指针时，同时记录当前子串的长度是否比之前记录的子串长度更短，如果是，则将当前子串的长度和起始位置记录下来，作为结果的可能。

这样，我们就可以在 $O(m + n)$ 的时间复杂度内解决此问题。

C++代码实现如下：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> t_map;
        for (const char& c : t) {
            ++t_map[c];
        }
        int left = 0, right = 0, count = t.length(), min_len = INT_MAX, min_start = 0;
        while (right < s.length()) {
            // 右指针右移
            if (t_map[s[right++]]-- > 0) {
                --count;
            }

            while (count == 0) {
                if (right - left < min_len) {
                    min_len = right - left;
                    min_start = left;
                }
                // 左指针左移
                if (t_map[s[left++]]++ == 0) {
                    ++count;
                }
            }
        }
        return min_len == INT_MAX ? "" : s.substr(min_start, min_len);
    }
};