Advertisement
imashutosh51

Minimum Window substring

Oct 29th, 2022
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. /*
  2. count is a map which will keep the each character count in string t because duplicate character can be in t.
  3. need is actually how many minimum characters must be present in window.
  4. winodw map will keep the store the count of characters in current window.
  5. if we get any character whose count in window is less than count of character in t then we got one needed
  6. character so decrease need and update the window map.
  7. if need==0 means we have all the needed characters in window,so we will update the answer.Now decrease the
  8. charcters from left and if you loose one needed one character then update the answer with including that lost
  9. character and now traverse ahead but we have need of one character.
  10. */
  11. class Solution {
  12. public:
  13.     string minWindow(string s, string t) {
  14.         unordered_map<char,int> count;
  15.         for(auto itr:t) count[itr]++;
  16.         int need=t.size();
  17.         int l=0;
  18.         unordered_map<char,int> window;
  19.         int ans=INT_MAX;
  20.         string _ans="";
  21.         for(int i=0;i<s.size();i++){
  22.             if(window[s[i]]<count[s[i]]){
  23.                 need--;
  24.             }
  25.             window[s[i]]++;
  26.             if(need==0){
  27.                 if(ans>(i-l+1)){ans=i-l+1;_ans=s.substr(l,i+1);}
  28.                 do{
  29.                     window[s[l]]--;
  30.                 }while(l<=i && window[s[l]]>=count[s[l++]]);
  31.                 if(ans>(i-l+1)){ans=i-l+2;_ans=s.substr(l-1,i-l+2);}
  32.             need++;
  33.             }
  34.         }
  35.         return _ans;
  36.            
  37.     }
  38. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement