Untitled
unknown
plain_text
2 years ago
1.1 kB
19
Indexable
class Solution {
public:
string minWindow(string str, string t) {
if(t=="") return "";
pair<int,int> res={-1,-1};
int i=0, j=0;
int nr=str.size();//fixed
unordered_map<char,int> n;
for(auto i:t) n[i]++; //fixed
unordered_map<char,int>window;
int l=0, reslen=INT_MAX;
int need=t.size(), have=0;
for(int r=0;r<nr;r++){
char c=str[r];
window[c]++;
if(n.find(c)!=n.end() && window[c]<=n[c]) have++;
while(have==need){ //shorten window now
if(r-l+1 < reslen){
res={l,r-l+1}; //starting index and length
reslen=r-l+1;
}
window[str[l]]--;
if(n.find(str[l])!= n.end() && window[str[l]] < n[str[l]]) have--;
l++;
}
}
if(res.first == -1) return "";
string ans=str.substr(res.first,res.second) ;
return ans;
}
};Editor is loading...
Leave a Comment