题目

给定一个字符串 s 和一个字符串 t，请你在 s 中找出 最小 的子串，使得该子串包含了 t 中的所有字符（包括重复字符）。如果不存在这样的子串，则返回空字符串 ""。

注意：

• 对于 t 中重复的字符，要求子串中该字符的数量必须不少于 t 中的数量。
• 如果存在这样的子串，我们保证它是唯一的答案。

---

示例 1

输入：
s = "ADOBECODEBANC", t = "ABC"

输出：
"BANC"

解释：
最小覆盖子串 "BANC" 包含了字符串 t 中的 'A'、'B' 和 'C'。

---

示例 2

输入：
s = "a", t = "a"

输出：
"a"

解释：
整个字符串 s 已经是满足条件的最小子串。

---

示例 3

输入：
s = "a", t = "aa"

输出：
""

解释：
t 中包含两个字符 'a'，但 s 中只有一个 'a'，因此不存在符合条件的子串。

---

数据范围

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s 和 t 由英文字母组成

实现

class Solution {
public:
    static bool check(int need[], int state[])
    {
        for(int i = 'a' ; i <= 'z' ; i++) if(state[i] < need[i]) return false;
        for(int i = 'A' ; i <= 'Z' ; i++) if(state[i] < need[i]) return false;
        return true;
    }
    string minWindow(string s, string t) {
        // 维护动态窗口 向右移动窗口 直到满足要求
        // 减少窗口的左断点 并且保证不会减少资源

        int need[200]{} , state[200]{};
        for(auto& c : t) need[c] ++;

        int i = 0 , j = 0;
        string res = "";
        bool flag = false;

        while(j < s.length())
        {
            state[s[j++]] ++;

            if (!flag && !Solution::check(need , state)) {
                continue;
            }
            flag = true; // 当第一次覆盖目标串,就一直会覆盖目标串

            while(i < j && (need[s[i]] == 0 || need[s[i]] < state[s[i]])) state[s[i++]] --;
            if (res == "" || res.length() > j - i) res = s.substr(i , j - i);
        }
        return res;
    }
};