1.最小覆盖子串
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:
如果 S 中不存这样的子串,则返回空字符串 ""。
如果 S 中存在这样的子串,我们保证它是唯一的答案。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-window-substring
思路:
图片说明 如何判断当前的窗口包含所有t所需的字符呢?我们可以用一个哈希表表示t中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含t的哈希表中的所有字符,并且对应的个数都不小于t的哈希表中各个字符的个数,那么当前的窗口是「可行」的。

class Solution {
public:
    unordered_map <char, int> ori, cnt;//构建两个哈希表,1记录t的字符,2动态记录窗口的字符

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }//如果cnt中字符的值小于ori中对应字符的值,返回false
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }//哈希表1记录t的字符
        int l = 0, r = -1;//双指针
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }//区间内找到一个相同的字符
            //符合要求的话,计算一下长度
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;//左指针收缩
            }
            //不符合要求,左不动,右右移
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};