76. 最小覆盖子串

🔴   🔖  哈希表 字符串 滑动窗口  🔗 力扣 LeetCode

题目

Given two strings s and t of lengths m and n respectively, return the minimum window substring ofs such that every character in t( including duplicates ) is included in the window. If there is no such substring, return the empty string"".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"

Output: "a"

Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"

Output: ""

Explanation: Both 'a's from t must be included in the window.

Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

题目大意

给定一个源字符串 s，再给一个字符串 t，要求在源字符串中找到一个窗口，这个窗口包含由字符串各种排列组合组成的，窗口中可以包含 t 中没有的字符，如果存在多个，在结果中输出最小的窗口，如果找不到这样的窗口，输出空字符串。

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

解题思路

如果我们使用暴力解法，代码大概是这样的：

for (let i = 0; i < s.length(); i++) {
    for (let j = i + 1; j < s.length(); j++) {
        if (s[i:j] 包含 t 的所有字母) {
            更新答案
        }
    }
}

思路很直接，但是显然，这个算法的复杂度大于 O(n^2) 了，不好。

滑动窗口算法的思路是这样：

1. 使用双指针中的左右指针，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」；
2. 不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 t 中的所有字符）；
3. 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 t 中的所有字符了）；同时，每次增加 left，都要更新一轮结果；
4. 重复第 2 和第 3 步，直到 right 到达字符串 s 的尽头；

第 2 步相当于在寻找一个「可行解」，第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，一伸一缩，不断向右滑动，这就是「滑动窗口」这个名字的来历。

详细的滑动窗口答题框架讲解，可阅读 《3.11 滑动窗口》。

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
	let need = new Map();
	let window = new Map();
	for (let i of t) {
		need.set(i, need.has(i) ? need.get(i) + 1 : 1);
	}

	let left = 0,
		right = 0,
		vaild = 0,
		start = 0,
		len = Infinity;
	while (right < s.length) {
		let i = s[right];
		right++;
		if (need.has(i)) {
			window.set(i, window.has(i) ? window.get(i) + 1 : 1);
			if (window.get(i) === need.get(i)) {
				vaild++;
			}
		}

		while (vaild === need.size) {
			if (right - left < len) {
				start = left;
				len = right - left;
			}
			let d = s[left];
			left++;
			if (need.has(d)) {
				if (window.get(d) === need.get(d)) {
					vaild--;
				}
				window.set(d, window.get(d) - 1);
			}
		}
	}
	return len === Infinity ? '' : s.slice(start, start + len);
};

相关题目

题号	标题	题解	标签	难度
30	串联所有单词的子串	[✓]	哈希表 字符串 滑动窗口
209	长度最小的子数组	[✓]	数组 二分查找 前缀和 1+
239	滑动窗口最大值	[✓]	队列 数组 滑动窗口 2+
567	字符串的排列	[✓]	哈希表 双指针 字符串 1+
632	最小区间	[✓]	贪心 数组 哈希表 3+
727	最小窗口子序列 🔒		字符串 动态规划 滑动窗口
3297	统计重新排列后包含另一个字符串的子字符串数目 I		哈希表 字符串 滑动窗口
3298	统计重新排列后包含另一个字符串的子字符串数目 II		哈希表 字符串 滑动窗口