Advertisement
fireLUFFY

Minimum Window Substring

May 29th, 2022
877
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     string minWindow(string s, string t) {
  4.         string ans="";
  5.        
  6.         if(s.size()==0 || t.size()==0)
  7.             return ans;
  8.        
  9.         if(t.size()>s.size())
  10.             return ans;
  11.        
  12.         unordered_map<char,pair<int,int>> mp;
  13.        
  14.         for(int i=0;i<t.size();i++){
  15.             mp[t[i]].first++;
  16.             mp[t[i]].second++;
  17.         }
  18.        
  19.         int l=0,r=0,len=INT_MAX,dc=0,ansl=0,ansr=0,idc=mp.size();
  20.         char c,cc;
  21.        
  22.         while(r<s.size()){
  23.             c=s[r];
  24.             mp[c].second--;
  25.            
  26.             if(mp[c].second==0 && mp[c].first!=0)
  27.                 dc++;
  28.            
  29.             while(dc==idc && l<=r){
  30.                 cc=s[l];
  31.                 if(len==INT_MAX || len>(r-l+1)){
  32.                     ansl=l;
  33.                     ansr=r;
  34.                     len=(ansr-ansl+1);
  35.                 }
  36.                
  37.                 mp[cc].second++;
  38.                 if(mp[cc].second>0 && mp[cc].first!=0)
  39.                     dc--;
  40.                
  41.                 l++;
  42.             }
  43.             r++;
  44.         }
  45.        
  46.         if(len!=INT_MAX){
  47.             for(int i=ansl;i<=ansr;i++){
  48.                 ans+=s[i];
  49.             }
  50.         }
  51.         return ans;
  52.     }
  53. };
Advertisement
RAW Paste Data Copied
Advertisement