今天我们看一道 leetcode hard 难度题目：最小覆盖子串。
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
代码语言：javascript复制输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
思考
最容易想到的思路是，s 从下标 0~n 形成的子串逐个判断是否满足条件，如：
- ADOBEC..
- DOBECO..
- OBECOD..
因为最小覆盖子串是连续的，所以该方法可以保证遍历到所有满足条件的子串。代码如下：
代码语言：javascript复制function minWindow(s: string, t: string): string {
// t 剩余匹配总长度
let tLeftSize = t.length
// t 每个字母对应出现次数表
const tCharCountMap = {}
for (const char of t) {
if (!tCharCountMap[char]) {
tCharCountMap[char] = 0
}
tCharCountMap[char]
}
let globalResult = ''
for (let i = 0; i < s.length; i ) {
let currentResult = ''
let currentTLeftSize = tLeftSize
const currentTCharCountMap = { ...tCharCountMap }
// 找到以 i 下标开头，满足条件的字符串
for (let j = i; j < s.length; j ) {
currentResult = s[j]
// 如果这一项在 t 中存在，则减 1
if (currentTCharCountMap[s[j]] !== undefined && currentTCharCountMap[s[j]] !== 0) {
currentTCharCountMap[s[j]]--
currentTLeftSize--
}
// 匹配完了
if (currentTLeftSize === 0) {
if (globalResult === '') {
globalResult = currentResult
} else if (currentResult.length < globalResult.length) {
globalResult = currentResult
}
break
}
}
}
return globalResult
};
我们用 tCharCountMap 存储 t 中每个字符出现的次数，在遍历时每次找到出现过的字符就减去 1，直到 tLeftSize 变成 0，表示 s 完全覆盖了 t。
这个方法因为执行了 n n-1 n-2 ... 1 次，所以时间复杂度是 O(n²)，无法 AC，因此我们要寻找更快捷的方案。
滑动窗口
追求性能的降级方案是滑动窗口或动态规划，该题目计算的是字符串，不适合用动态规划。
那滑动窗口是否合适呢？
该题要计算的是满足条件的子串，该子串肯定是连续的，滑动窗口在连续子串匹配问题上是不会遗漏结果的，所以肯定可以用这个方案。
思路也很容易想，即：如果当前字符串覆盖 t，左指针右移，否则右指针右移。就像一个窗口扫描是否满足条件，需要右指针右移判断是否满足条件，满足条件后不一定是最优的，需要左指针继续右移找寻其他答案。
这里有一个难点是如何高效判断当前窗口内字符串是否覆盖 t，有三种想法：
第一种想法是对每个字符做一个计数器，再做一个总计数器，每当匹配到一个字符，当前字符计数器与总计数器 1，这样直接用总计数器就能判断了。但这个方法有个漏洞，即总计数器没有包含字符类型，比如连续匹配 100 个 b，总计数器都 1，此时其实缺的是 c，那么当 c 匹配到了之后，总计数器的值并不能判定出覆盖了。
第一种方法的优化版本可能是二进制，比如用 26 个 01 表示，但可惜每个字符出现的次数会超过 1，并不是布尔类型，所以用这种方式取巧也不行。
第二种方法是笨方法，每次递归时都判断下 s 字符串当前每个字符收集的数量是否超过 t 字符串每个字符出现的数量，坏处是每次递归都至多多循环 25 次。
笔者想到的第三种方法是，还是需要一个计数器，但这个计数器 notCoverChar 是一个 Set<string> 类型，记录了每个 char 是否未 ready，所谓 ready 即该 char 在当前窗口内出现的次数 >= 该 char 在 t 字符串中出现的次数。同时还需要有 sCharMap、tCharMap 来记录两个字符串每个字符出现的次数，当右指针右移时，sCharMap 对应 char 计数增加，如果该 char 出现次数超过 t 该 char 出现次数，就从 notCoverChar 中移除；当左指针右移时，sCharMap 对应 char 计数减少，如果该 char 出现次数低于 t 该 char 出现次数，该 char 重新放到 notCoverChar 中。
代码如下：
代码语言：javascript复制function minWindow(s: string, t: string): string {
// s 每个字母出现次数表
const sCharMap = {}
// t 每个字母对应出现次数表
const tCharMap = {}
// 未覆盖的字符有哪些
const notCoverChar = new Set<string>()
// 计算各字符在 t 出现次数
for (const char of t) {
if (!tCharMap[char]) {
tCharMap[char] = 0
}
tCharMap[char]
notCoverChar.add(char)
}
let leftIndex = 0
let rightIndex = -1
let result = ''
let currentStr = ''
// leftIndex | rightIndex 超限才会停止
while (leftIndex < s.length && rightIndex < s.length) {
// 未覆盖的条件：notCoverChar 长度 > 0
if (notCoverChar.size > 0) {
// 此时窗口没有 cover t，rightIndex 右移寻找
rightIndex
const nextChar = s[rightIndex]
currentStr = nextChar
if (sCharMap[nextChar] === undefined) {
sCharMap[nextChar] = 0
}
sCharMap[nextChar]
// 如果 tCharMap 有这个 nextChar, 且已收集数量超过 t 中数量，此 char ready
if (
tCharMap[nextChar] !== undefined &&
sCharMap[nextChar] >= tCharMap[nextChar]
) {
notCoverChar.delete(nextChar)
}
} else {
// 此时窗口正好 cover t，记录最短结果
if (result === '') {
result = currentStr
} else if (currentStr.length < result.length) {
result = currentStr
}
// leftIndex 即将右移，将 sCharMap 中对应 char 数量减 1
const previousChar = s[leftIndex]
sCharMap[previousChar]--
// 如果 previousChar 在 sCharMap 数量少于 tCharMap 数量，则不能 cover
if (sCharMap[previousChar] < tCharMap[previousChar]) {
notCoverChar.add(previousChar)
}
// leftIndex 右移
leftIndex
currentStr = currentStr.slice(1, currentStr.length)
}
}
return result
};
其中还用了一些小缓存，比如 currentStr 记录当前窗口内字符串，这样当可以覆盖 t 时，随时可以拿到当前字符串，而不需要根据左右指针重新遍历。
总结
该题首先要排除动态规划，并根据连续子串特性第一时间想到滑动窗口可以覆盖到所有可能性。
滑动窗口方案想到后，需要想到如何高性能判断当前窗口内字符串可以覆盖 t，notCoverChar 就是一种不错的思路。
讨论地址是：精读《算法 - 最小覆盖子串》· Issue #496 · dt-fe/weekly
如果你想参与讨论，请 点击这里，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。
版权声明：自由转载-非商用-非衍生-保持署名（创意共享 3.0 许可证）
