LeetCode 076 Minimum Window Substring

LeetCode

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.

A substring is a contiguous sequence of characters within the string.

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<sup>5</sup> 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的字符的最短子串。这个结果可以包含不在t的字符，某个字符数量也可以多于t中的字符但不能少于。

解题思路：

提到window substring就用滑动窗口或者同向双指针。

解题步骤：

N/A

注意事项：

1. 用同向双指针模板。用map来统计t的字符频率，用unique_count统计满足条件唯一字符个数。while的条件为unique_count达到了map的大小。
2. while里面的统计与while外面的统计本质一样，但相反。若s中某字符多于s中的，map为负值，left指针右移时，负值会变回正值。

Python代码：

def minWindow(self, s: str, t: str) -> str:
	t_char_to_count = collections.Counter(t)
	left, unique_count, min_len, res = 0, 0, float('inf'), ''
	for i in range(len(s)):
		if s[i] in t_char_to_count:
			t_char_to_count[s[i]] -= 1
			if t_char_to_count[s[i]] == 0:
				unique_count += 1
		while unique_count == len(t_char_to_count):
			if i - left + 1 < min_len:
				min_len = i - left + 1
				res = s[left:i + 1]
			if s[left] in t_char_to_count:
				t_char_to_count[s[left]] += 1
				if t_char_to_count[s[left]] == 1:
					unique_count -= 1
			left += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(m), n和m分别为s和t的长度