最小覆盖子串

# 题目

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。

说明:

如果 S 中不存这样的子串,则返回空字符串 ""。 如果 S 中存在这样的子串,我们保证它是唯一的答案。

# 示例

示例:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

# 题解

# 思路

  • 初始化时先将left、right两个指针指向下标0,然后将right右移,直到到达字符串T末尾

  • 移动过程中,我们需要收集并计算left~right中还缺失的字符类型个数,记为 missing

  • 当missing为0的时候,尝试去将left右移,以缩小left~right这个窗口

  • 直到不能缩小时,当前left即为以right结尾的最小覆盖子串的起始下标,然后尝试和之前的长度进行比较并更新

为什么记录缺失,而不是记录当前拥有个数

如果只是记录拥有个数,那么在比对是否覆盖时,就需要遍历所有字符来比较。

但如果另外再记录缺失类型个数,这个值可以在扩大/缩小窗口时直接计算得到,方便下次直接比对

# 代码实现

function minWindow (s, t) {
  let ans = ''
  let left = -1
  const map = new Map()
  let missing = 0

  // 收集所有缺失字符
  for (let i = 0; i < t.length; i++) {
    const char = t[i]
    if (!map.has(char)) {
      map.set(char, 0)
      missing++
    }
    map.set(char, map.get(char) + 1)
  }

  for (let right = 0; right < s.length; right++) {
    const char = s[right]
    if (!map.has(char)) {
      continue
    }
    // 缺失字符递减
    map.set(char, map.get(char) - 1)
    if (map.get(char) === 0) { // 从 1 -> 0时,缺失字符才减1,-1 -> -2 不能算缺失减1,所以这里必须是等号,不能是小于号
      missing--
    }

    if (missing > 0) {
      continue
    }

    // 尝试往右移动left指针缩小窗口
    while (missing === 0) {
      const char = s[left]
      left++
      if (!map.has(char)) {
        continue
      }
      map.set(char, map.get(char) + 1)
      if (map.get(char) > 0) {
        missing++
      }
    }
    if (right - (left - 1) + 1 < ans.length || !ans) {
      ans = s.substring(left - 1, right + 1)
    }
  }

  return ans
}