给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

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

思路

  1. 字符计数判定是否存在目标子串
  2. 通过滑动窗口求解
  3. 使用 checkKeyChar 方法和 matchCount 优化对合法字符串的判定
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
var minWindow = function (s, t) {
  const tCounts = t.split('').reduce((result, char) => {
    result[char] = (result[char] || 0) + 1
    return result
  }, {})
  const sCounts = {}
  let matchCount = 0
  let [left, right] = [0, 1]
  let result = s + '!'
  const checkKeyChar = (char) => tCounts[char] && sCounts[char] <= tCounts[char]
  while (right <= s.length) {
    const rightChar = s[right - 1]
    sCounts[rightChar] = (sCounts[rightChar] || 0) + 1
    if (checkKeyChar(rightChar)) {
      ++matchCount
    }
    while (left < right && !checkKeyChar(s[left])) {
      --sCounts[s[left]]
      ++left
    }
    if (matchCount === t.length && right - left < result.length) {
      result = s.substring(left, right)
    }
    ++right
  }
  return result.length > s.length ? '' : result
}