76\. Minimum Window Substring
# 76. Minimum Window Substring (opens new window)
# Description
Difficulty: Hard
Related Topics: Hash Table (opens new window), String (opens new window), Sliding Window (opens new window)
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.
1
2
3
2
3
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
1
2
3
2
3
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.
1
2
3
4
2
3
4
Constraints:
m == s.length
n == t.length
- 1 <= m, n <= 105
s
andt
consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n)
time?
# Solution
Language: JavaScript
/**
* @param {string} s
* @param {string} t
* @return {string}
* 子串强调了[连续性]
* T中可能包含重复字符
* 1.暴力解法
* 枚举输入字符串S的所有长度大于等于T的子串
* 逐个判断这些子串中,哪些子串覆盖了字符串T的所有字符;
* 在枚举的过程中,记录符合条件的,长度最短的那个子串。
*
* 如何判断S的子串包含了T中的所有字符?
* 参考做法:分别统计S的子串和T中每个字符出现的次数,然后逐个比对。
* 字符频数数组
*/
var minWindow = function(s, t) {
const cnt = new Array(128).fill(0);
let [start, end] = [-Infinity, Infinity];
let [left, right, count] = [0, 0, t.length];
for (let i = 0; i < t.length; i++)
cnt[t.charCodeAt(i)]++;
while (right < s.length) {
if (cnt[s.charCodeAt(right)]-- > 0) count--;
while (!count) {
if (end - start > right - left) [start, end] = [left, right];
if (++cnt[s.charCodeAt(left++)] > 0) count++;
}
right++;
}
return end === Infinity ? '' : s.substring(start, end + 1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36