Open
Description
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 中此字符出现的次数。
窗口滑动逻辑：
- 如果当前还没有能覆盖，那么就右滑右边界。
- 如果当前已经覆盖了，记录下当前的子串，并且右滑左边界看看能否进一步缩小子串的长度。
两种情况下停止循环，返回结果：
- 左边界达到
给定字符长度 - 目标字符的长度，此时不管匹配与否，都是最短能满足的了。 - 右边界超出给定字符的长度，这种情况会出现在右边界已经到头了，但是还没有能覆盖目标字符串，此时就算继续滑动也不可能得到结果了。
/**
* @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"))