[LeetCode] 76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window
substring of s 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 <= 105
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 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路依然是滑动窗口（sliding window），这个题解是具有普适性的，可以套用到多个 LC 的题目中。如下是几个细节，

• 创建一个hashmap，记录T中出现的字母及其次数
• 创建一个变量count去记录T的长度
• 创建两个指针left和right，一前一后扫描S，right在前，left在后，去卡S里面的子串，看这个子串里面是否包含T中所有的字符
• 最后跳出循环的条件是right已经扫描完整个S的长度

扫描的一开始，是 right 指针往前走，每遇到一个字符，无论他在不在 T 中，就都去 map 中 – 这个字符；如果这个字符在 T 中也有，同时也要去 count–。当 count == 0 的时候，证明此时的子串已经包含了 T 中所有的字母了，可以考虑缩减 start 和 end 之间的距离了。缩减的条件是 while (count == 0)，去看 end - start 是否能缩短那个最小长度 minLen，同时开始挪动 start 指针；若能缩短，也要记录一个变量 minStart，这样就能记住最短的子串到底从什么位置开始的。挪动 start 指针的时候也要去 map 中补足当前遍历到的字符的出现次数。如果当前字符在 map 中的 value 大于 0 了，count 也需要++，因为这说明有一个字符已经不在子串中了，此时会跳出 while 循环。最后最短子串是 s.substring(minStart, minStart + minLen)。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
	public String minWindow(String s, String t) {
		int[] map = new int[256];
		for (char c : t.toCharArray()) {
			map[c]++;
		}
		// end指针在右边，start指针在左边
		int start = 0;
		int end = 0;
		// 最短子串的起点
		int minStart = 0;
		// 最短子串的长度
		int minLen = Integer.MAX_VALUE;
		int counter = t.length();
		while (end < s.length()) {
			char c1 = s.charAt(end);
			if (map[c1] > 0) {
				counter--;
			}
			map[c1]--;
			end++;
			// 如果找到了所有t中的字符，可以试着缩小窗口的距离了
			while (counter == 0) {
				// 试图更新最短子串的长度和起点
				if (minLen > end - start) {
					minLen = end - start;
					minStart = start;
				}
				char c2 = s.charAt(start);
				map[c2]++;
				start++;
				if (map[c2] > 0) {
					counter++;
				}
			}
		}
		return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
	}
}

JavaScript实现

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
	let ans = '';
	// save all the letters in t to a hashmap
	let map = {};
	t.split('').forEach(ch => (map[ch] = (map[ch] || 0) + 1));
	let count = Object.keys(map).length;

	// traverse s
	let l = 0;
	let r = -1;
	while (r < s.length) {
		if (count === 0) {
			// l~r contains t
			if (!ans || r - l + 1 < ans.length) {
				ans = s.slice(l, r + 1);
			}
			// get rid of curr ch and then move l
			if (map[s[l]] !== undefined) {
				map[s[l]]++;
			}
			if (map[s[l]] > 0) {
				count++;
			}
			l++;
		} else {
			// l~r doesn't contain t
			// move r and add new ch
			r++;
			if (map[s[r]] !== undefined) {
				map[s[r]]--;
			}
			if (map[s[r]] === 0) {
				count--;
			}
		}
	}
	return ans;
};