最小覆盖子串-76

[sl1673495]

76.最小覆盖子串

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

示例：

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

说明：

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

https://leetcode-cn.com/problems/minimum-window-substring

思路

根据目标字符串 t生成一个目标 map，记录每个字符的目标值出现的次数。 然后就是维护一个滑动窗口，并且针对这个滑动窗口中的字符也生成一个 map 去记录字符出现次数。

每次循环都去对比窗口的 map 里的字符是否能覆盖目标 map 里的字符。

覆盖的意思就是，目标 map 里的每个字符在窗口 map 中出现，并且出现的次数要 >= 目标 map 中此字符出现的次数。

窗口滑动逻辑：

1. 如果当前还没有能覆盖，那么就右滑右边界。
2. 如果当前已经覆盖了，记录下当前的子串，并且右滑左边界看看能否进一步缩小子串的长度。

两种情况下停止循环，返回结果：

1. 左边界达到 给定字符长度 - 目标字符的长度，此时不管匹配与否，都是最短能满足的了。
2. 右边界超出给定字符的长度，这种情况会出现在右边界已经到头了，但是还没有能覆盖目标字符串，此时就算继续滑动也不可能得到结果了。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
let minWindow = function (s, t) {
  // 先制定目标 根据t字符串统计出每个字符应该出现的个数
  let targetMap = makeCountMap(t)

  let sl = s.length
  let tl = t.length
  let left = 0 // 左边界
  let right = -1 // 右边界
  let countMap = {} // 当前窗口子串中 每个字符出现的次数
  let min = "" // 当前计算出的最小子串

  // 循环终止条件是两者有一者超出边界
  while (left <= sl - tl && right <= sl) {
    // 和 targetMap 对比出现次数 确定是否满足条件
    let isValid = true
    Object.keys(targetMap).forEach((key) => {
      let targetCount = targetMap[key]
      let count = countMap[key]
      if (!count || count < targetCount) {
        isValid = false
      }
    })

    if (isValid) {
      // 如果满足 记录当前的子串 并且左边界右移
      let currentValidLength = right - left + 1
      if (currentValidLength < min.length || min === "") {
        min = s.substring(left, right + 1)
      }
      // 也要把map里对应的项去掉
      countMap[s[left]]--
      left++
    } else {
      // 否则右边界右移
      addCountToMap(countMap, s[right + 1])
      right++
    }
  }

  return min
}

function addCountToMap(map, str) {
  if (!map[str]) {
    map[str] = 1
  } else {
    map[str]++
  }
}

function makeCountMap(strs) {
  let map = {}
  for (let i = 0; i < strs.length; i++) {
    let letter = strs[i]
    addCountToMap(map, letter)
  }
  return map
}

console.log(minWindow("aa", "a"))