76. 最小覆盖子串
难度困难1312
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
双指针，第一重循环移动右指针，如果此时左右指针围成的字符串满足条件则更新答案，然后移动左指针，再进行判断再移动...最后输出存下来的长度最小的子串即可（根据保存的左右指针位置输出）。判断合法性可以用桶判断，即代码里的chech函数，注意这个题大小写都有。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int cnt[128];
int now[128];
int mmin = 0x3f3f3f3f, ansl, ansr;
bool check() {
for(int i = 0; i < 128; i++) {
if(now[i] < cnt[i]) return 0;
}
return 1;
}
string minWindow(string s, string t) {
memset(cnt, 0, sizeof(cnt));
int l = 0, r = 0;
int len1 = s.size(), len2 = t.size();
for(int i = 0; i < len2; i++) {
cnt[(int)t[i]]++;
}
memset(now, 0, sizeof(now));
for(r = 0; r < len1; r++) {
now[(int)s[r]]++;
if(check()) {
//cout << "fck" << endl;
int len = r - l + 1;
//cout << len << endl;
if(len < mmin) {
mmin = len;
ansl = l;
ansr = r;
}
now[(int)s[l]]--;
l++;
while(check()) {
int len = r - l + 1;
if(len < mmin) {
mmin = len;
ansl = l;
ansr = r;
}
now[(int)s[l]]--;
l++;
}
} else {
continue;
}
}
if(mmin == 0x3f3f3f3f) return "";
return s.substr(ansl, mmin);
}
} slu;
int main() {
string s1 ,s2;
cin >> s1;
cin >> s2;
cout << slu.minWindow(s1, s2) << endl;
return 0;
}