Untitled
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