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

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
1
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

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?

# 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
上次更新: 2022/7/14 下午7:06:25