Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
A substring is a contiguous sequence of characters within the string.
Solution
我们首先用 \(map\) 来记录 \(t\) 中字符出现的次数。然后用左右指针分别移动
点击查看代码
class Solution {
private:
string ans="";
unordered_map<char,int> mp;
int min_len=INT_MAX;
int st_ans=0;
public:
string minWindow(string s, string t) {
int m = s.size(), n = t.size();
if(m<n)return ans;
int l=0,h=0;
int cnt=0;
for(auto ele:t)mp[ele]++;
for(h=0;h<m;h++){
if(mp[s[h]]>0)cnt++;//means that this letter is in t
mp[s[h]]--;
if(cnt==n){
while(l<h && mp[s[l]]<0){mp[s[l]]++;l++;}
if(min_len>h-l+1){
min_len = h-l+1;st_ans=l;
}
mp[s[l]]++;l++;
cnt--;
}
}
return min_len==INT_MAX?"":s.substr(st_ans,min_len);
}
};