给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 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 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
s 和 t 由英文字母组成
进阶:你能设计一个在
思路:双指针 + 哈希表
- 通过哈希表记录 t 串每个字符出现的次数
- dif 记录(当前子串,距离覆盖 t 串)差多少个覆盖字符(对于覆盖的字符,必须满足,c 属于t,并且c属于子串,并且子串的sub_cnt[c] >= t_cnt[c] )
- r 是子串的区间右边界,l 是子串的左边界
- 假如当前子串没有覆盖 t 串,则 r 右移,直到覆盖
- 假如当前子串覆盖,则 l 右移,找出最小的覆盖串
时间复杂度:
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> h;
int dif = t.size();
for(int i = 0; i < t.size(); i++) h[t[i]]++;
string res = "";
int start = 0, end = -1;
int l = 0, r = -1;
int n = s.size();
for(int r = 0; r < n; r++){
if(h.count(s[r])){
if(h[s[r]] > 0) dif--;
h[s[r]]--;
}
while(dif == 0 && l <= r){
if(end == -1) start = l, end = r;
else if((r - l) < (end - start)){
start = l, end = r;
}
l++;
if(h.count(s[l - 1])) {
h[s[l-1]]++;
if(h[s[l-1]] >= 1) dif++;
}
}
}
if(end != -1) res = s.substr(start, end - start + 1);
return res;
}
};