题解 | #最小覆盖子串#

如何利用滑动窗口寻找最小覆盖子串？

• 利用双指针实现一个滑动窗口，初始时左右指针都指向数组开头，开始寻找时右指针开始移动，直到满足某个条件时停下，此时左右指针构造的滑动窗口就满足了题目条件所需内容。为了进一步达到最小条件要求，需要移动左指针缩小窗口，直到不满足条件时，再移动右指针寻找满足条件的窗口，直到右指针达到数组末尾，每次达到满足条件的窗口时，都更新所要求的最值状态。
• 本题初始时左右指针指向S的字符串开头，右指针移动寻找能够覆盖T字符串中所有字符的窗口，如果找到后，则更新当前窗口为最小覆盖子串，为了得到全局最小覆盖子串，需要再移动左指针缩小窗口使窗口中不能覆盖T字符串中的所有字符，此时右指针再继续移动寻找下一个能够覆盖T字符串中所有字符的窗口，并更新最小覆盖子串，直到右指针达到S字符串的末尾。

如何利用哈希表快速判断某个元素是否出现过？

• 需要维护两个哈希表，键为字符串T中的字符，值为该字符的出现次数，其中一个哈希表保存T字符串中所有字符的出现次数，另一个哈希表保存滑窗中T字符串中所有字符的出现次数。
• 初始时遍历T中的所有字符，将各字符的出现次数统计在哈希表中，然后遍历S字符串的滑窗，看里面的字符是否在T的哈希表中，如果在说明该字符是T中的字符，所以要在滑窗哈希表中统计该字符的出现次数。由于一个字符可能出现多次，因此只有当两个哈希表中的字符出现次数相等时，才能认为滑窗中完全包含了该字符，此时增加一个字符计数。当字符计数达到T中的字符种类数时，说明此时滑窗中已经包含全部T中的字符了，此时要缩小窗口，更新最小覆盖子串。
• 滑窗中出现T中的字符时都会计数，在达到T中的该字符个数时增加字符种类，但之后还是可能再遇到该字符，仍然进行计数，也就是滑窗中出现T的字符可能会超过T中该字符的个数，所以在缩小窗口时，只有该字符数量减少到和T中该字符数量相等时，才能认为滑窗中不包含该字符，此时减少滑窗中的该字符种类计数。

参考

https://blog.nowcoder.net/n/1a15814e64704bdfa8349586356e63f1?f=comment

https://blog.nowcoder.net/n/a8b8988da1564ca2b309449ca79dc018?f=comment

/*
 * @Author: LibraStalker **********
 * @Date: 2023-04-24 22:17:18
 * @FilePath: BM90-最小覆盖子串.js
 * @Description: 
 */

/**
  * 
  * @param S string字符串 
  * @param T string字符串 
  * @return string字符串
  */
function minWindow( S ,  T ) {
    // write code here
    const T_hashCount = {};  // 统计T中每个字符的数量
    const S_hashCount = {};  // 统计滑窗中出现T中的字符的数量

    for (let i = 0; i < T.length; ++i) {
        if (T_hashCount.hasOwnProperty(T[i])) {
            T_hashCount[T[i]]++;  // T中可能有重复的字符，每出现一个计数一次
        }
        else {
            T_hashCount[T[i]] = 1;
        }
    }
    for (let i = 0; i < T.length; ++i) {
        S_hashCount[T[i]] = 0;
    }

    let minLength = Infinity;
    let left = 0;
    let right = 0;
    let count = 0;  // 判断滑窗中是否包含了T中所有字符的种类和个数
    let resString = "";

    while (right < S.length) {
        if (T_hashCount.hasOwnProperty(S[right])) {  // 说明S[right]是T中的字符
            S_hashCount[S[right]]++;
            if (S_hashCount[S[right]] === T_hashCount[S[right]]) {  // 如果滑窗中出现的T中的字符达到T中该字符的数量，则这个滑窗包含了这个字符
                ++count;
            }
        }

        ++right;
        while (count === Object.keys(T_hashCount).length) {
            if ((right - left) <= minLength) {
                minLength = right - left;
                resString = S.substring(left, right);
            }

            if (T_hashCount.hasOwnProperty(S[left])) {
                if (S_hashCount[S[left]] === T_hashCount[S[left]]) {  // 如果滑窗中出现的T中的字符达到T中该字符的数量，则这个滑窗包含了这个字符
                    --count;
                }
                S_hashCount[S[left]]--;
            }
            ++left;  // 缩小窗口直至不完全包含T中的全部字符
        }
        
    }

    return resString;
}

module.exports = {
    minWindow : minWindow
};