76. Minimum Window Substring

76. Minimum Window Substringopen in new window

🔴 🔖 哈希表 字符串 滑动窗口 🔗 LeetCodeopen in new window

题目

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) 了，不好。

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

使用双指针中的左右指针，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」；
不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 t 中的所有字符）；
停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 t 中的所有字符了）；同时，每次增加 left，都要更新一轮结果；
重复第 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);
};

76. Minimum Window Substring

# 76. Minimum Window Substringopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

76. Minimum Window Substringopen in new window

题目

题目大意

解题思路

代码

相关题目