Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- count is a map which will keep the each character count in string t because duplicate character can be in t.
- need is actually how many minimum characters must be present in window.
- winodw map will keep the store the count of characters in current window.
- if we get any character whose count in window is less than count of character in t then we got one needed
- character so decrease need and update the window map.
- if need==0 means we have all the needed characters in window,so we will update the answer.Now decrease the
- charcters from left and if you loose one needed one character then update the answer with including that lost
- character and now traverse ahead but we have need of one character.
- */
- class Solution {
- public:
- string minWindow(string s, string t) {
- unordered_map<char,int> count;
- for(auto itr:t) count[itr]++;
- int need=t.size();
- int l=0;
- unordered_map<char,int> window;
- int ans=INT_MAX;
- string _ans="";
- for(int i=0;i<s.size();i++){
- if(window[s[i]]<count[s[i]]){
- need--;
- }
- window[s[i]]++;
- if(need==0){
- if(ans>(i-l+1)){ans=i-l+1;_ans=s.substr(l,i+1);}
- do{
- window[s[l]]--;
- }while(l<=i && window[s[l]]>=count[s[l++]]);
- if(ans>(i-l+1)){ans=i-l+2;_ans=s.substr(l-1,i-l+2);}
- need++;
- }
- }
- return _ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement