Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- string minWindow(string s, string t) {
- string ans="";
- if(s.size()==0 || t.size()==0)
- return ans;
- if(t.size()>s.size())
- return ans;
- unordered_map<char,pair<int,int>> mp;
- for(int i=0;i<t.size();i++){
- mp[t[i]].first++;
- mp[t[i]].second++;
- }
- int l=0,r=0,len=INT_MAX,dc=0,ansl=0,ansr=0,idc=mp.size();
- char c,cc;
- while(r<s.size()){
- c=s[r];
- mp[c].second--;
- if(mp[c].second==0 && mp[c].first!=0)
- dc++;
- while(dc==idc && l<=r){
- cc=s[l];
- if(len==INT_MAX || len>(r-l+1)){
- ansl=l;
- ansr=r;
- len=(ansr-ansl+1);
- }
- mp[cc].second++;
- if(mp[cc].second>0 && mp[cc].first!=0)
- dc--;
- l++;
- }
- r++;
- }
- if(len!=INT_MAX){
- for(int i=ansl;i<=ansr;i++){
- ans+=s[i];
- }
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement