Advertisement
Kali_prasad

Minimum window substring TLE O(n+m)

Aug 26th, 2022
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.72 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int find_ind(char curr_char)
  4.     {
  5.         int ind=0;
  6.         if(isupper(curr_char))
  7.         {
  8.            ind=26+(curr_char-'A');
  9.         }
  10.         else
  11.         {
  12.             ind=curr_char-'a';
  13.         }
  14.         return ind;
  15.     }
  16.     bool comp(vector<int> &vs,vector<int> &vt,char curr_char)
  17.     {
  18.         int ind=find_ind(curr_char);
  19.         if(vs[ind]==vt[ind]) return true;
  20.         else                return false;
  21.     }
  22.     bool less(vector<int> &vs,vector<int> &vt,char curr_char)
  23.     {
  24.         int ind=find_ind(curr_char);
  25.         if(vs[ind]==vt[ind]-1) return true;
  26.         else                return false;
  27.     }
  28.     bool find_vt(vector<int> &vt,char curr_char)
  29.     {
  30.         int ind=find_ind(curr_char);
  31.         if(vt[ind]>0) return 1;
  32.         return 0;
  33.     }
  34.     void change(vector<int> &v,string str,int ind,int val)
  35.     {
  36.         if(isupper(str[ind]))
  37.         {
  38.           // cout<< v[(str[ind]-'A')+26]<<" ";
  39.             v[(str[ind]-'A')+26]+=val;
  40.            // cout<<v[(str[ind]-'A')+26]<<endl;
  41.         }
  42.         else
  43.         {
  44.          // cout<<  v[str[ind]-'a']<<" ";
  45.             v[str[ind]-'a']+=val;
  46.          // cout<<  v[str[ind]-'a']<<endl;
  47.         }
  48.     }
  49.    
  50.     string minWindow(string s, string t) {
  51.     vector<int> vs(52,0),vt(52,0) ;
  52.     int m=t.size();
  53.     for(int i=0;i<m;i++)
  54.     {
  55.         change(vt,t,i,1);//incrementing by 1
  56.     }
  57.     int required=0;
  58.     for(auto x:vt) if(x) required++;
  59.     int n=s.size();
  60.     int left=-1,right=0;
  61.     string ans="",finalans="";
  62.     bool nextdec=false;
  63.     char curr_char;
  64.     int have=0;
  65.     while(left<right&&right<n)
  66.     {
  67.        
  68.         if(nextdec)
  69.         {
  70.             change(vs,s,left,-1);//decrementing by 1
  71.             curr_char=s[left];
  72.             if(less(vs,vt,curr_char)) have--;
  73.            
  74.         }    
  75.         else
  76.         {
  77.              change(vs,s,right,1);//incrementing by 1
  78.              curr_char=s[right];
  79.              if(comp(vs,vt,curr_char)) have++;
  80.            
  81.         }
  82.         nextdec=false;//releasing if locked
  83.         if(have==required)
  84.         {
  85.              {
  86.                 finalans=ans;
  87.                 ans=s.substr(left+1,right-left);
  88.                 int fanssz=finalans.size();
  89.                 if(fanssz)
  90.                 {
  91.                     if(fanssz<ans.size())//choosing the minimum answer
  92.                         ans=finalans;
  93.                 }
  94.                
  95.                
  96.              }
  97.             nextdec=true;//locking the next iterartion to be as a decrement one
  98.             left++;
  99.         }
  100.         else
  101.         {
  102.             right++;
  103.         }
  104.        // cout<<ans<<endl;
  105.        
  106.     }
  107.         return ans;
  108.     }
  109. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement