题目链接
剑指 Offer II 017. 含有所有字符的最短字符串 hard
题目描述
给定两个字符串 s
和 t
。返回 s
中包含 t
的所有字符的最短子字符串。如果 s
中不存在符合条件的子字符串,则返回空字符串 ""
。
如果 s
中存在多个符合条件的子字符串,返回任意一个。
注意: 对于 t
中重复字符,我们寻找的子字符串中该字符数量必须不少于 t
中该字符数量。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’
示例 2:
输入:s = “a”, t = “a”
输出:“a”
示例 3:
输入:s = “a”, t = “aa”
输出:“”
解释:t 中两个字符 ‘a’ 均应包含在 s 的子串中,因此没有符合条件的子字符串,返回空字符串。
提示:
- 1 < = s . l e n g t h , t . l e n g t h < = 1 0 5 1 <= s.length, t.length <= 10^5 1<=s.length,t.length<=105
s
和t
由英文字母组成
分析:
本题用 滑动窗口 求解。
用哈希表 ht
记录 t
中字符的出现次数。
再用另一个哈希表 hs
记录 s
滑动窗口区间的字符出现次数。
用两个指针 i
和 j
分别维护滑动窗口的左边界 和 右边界。
如果 hs[s[j]] <= ht[s[j]]
,说明此时的 s[j]
依旧是有效字符,区间有效字符数 cnt += 1
。
如果 hs[s[i]] > ht[s[i]]
,说明此时的区间内部字符已经超过了 t
,所以收缩左区间,hs[s[i]]--
,i++
。
如果 cnt == t.size()
,说明此时的区间 [l,r]
包含了 t
的所有字符,所以此时的 s.substr(i,j-i+1)
可作为答案之一。
时间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
public:
string minWindow(string s, string t) {
int m = s.size() , n = t.size();
if(m < n) return "";
unordered_map<char,int> ht,hs;
for(auto &c:t) ht[c]++;
int len = 1e9,idx = -1;
int cnt = 0;
for(int i = 0,j = 0;j < m;j++){
hs[s[j]]++;
if(hs[s[j]] <= ht[s[j]]) cnt++;
while(hs[s[i]] > ht[s[i]]){
hs[s[i]]--;
i++;
}
if(cnt == n){
if(j - i + 1 < len){
idx = i;
len = j - i + 1;
}
}
}
return idx == -1 ? "" : s.substr(idx,len);
}
};