Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
2
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;   
    }
};
Leave a Comment