Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int find_ind(char curr_char)
- {
- int ind=0;
- if(isupper(curr_char))
- {
- ind=26+(curr_char-'A');
- }
- else
- {
- ind=curr_char-'a';
- }
- return ind;
- }
- bool comp(vector<int> &vs,vector<int> &vt,char curr_char)
- {
- int ind=find_ind(curr_char);
- if(vs[ind]==vt[ind]) return true;
- else return false;
- }
- bool less(vector<int> &vs,vector<int> &vt,char curr_char)
- {
- int ind=find_ind(curr_char);
- if(vs[ind]==vt[ind]-1) return true;
- else return false;
- }
- bool find_vt(vector<int> &vt,char curr_char)
- {
- int ind=find_ind(curr_char);
- if(vt[ind]>0) return 1;
- return 0;
- }
- void change(vector<int> &v,string str,int ind,int val)
- {
- if(isupper(str[ind]))
- {
- // cout<< v[(str[ind]-'A')+26]<<" ";
- v[(str[ind]-'A')+26]+=val;
- // cout<<v[(str[ind]-'A')+26]<<endl;
- }
- else
- {
- // cout<< v[str[ind]-'a']<<" ";
- v[str[ind]-'a']+=val;
- // cout<< v[str[ind]-'a']<<endl;
- }
- }
- string minWindow(string s, string t) {
- vector<int> vs(52,0),vt(52,0) ;
- int m=t.size();
- for(int i=0;i<m;i++)
- {
- change(vt,t,i,1);//incrementing by 1
- }
- int required=0;
- for(auto x:vt) if(x) required++;
- int n=s.size();
- int left=-1,right=0;
- string ans="",finalans="";
- bool nextdec=false;
- char curr_char;
- int have=0;
- while(left<right&&right<n)
- {
- if(nextdec)
- {
- change(vs,s,left,-1);//decrementing by 1
- curr_char=s[left];
- if(less(vs,vt,curr_char)) have--;
- }
- else
- {
- change(vs,s,right,1);//incrementing by 1
- curr_char=s[right];
- if(comp(vs,vt,curr_char)) have++;
- }
- nextdec=false;//releasing if locked
- if(have==required)
- {
- {
- finalans=ans;
- ans=s.substr(left+1,right-left);
- int fanssz=finalans.size();
- if(fanssz)
- {
- if(fanssz<ans.size())//choosing the minimum answer
- ans=finalans;
- }
- }
- nextdec=true;//locking the next iterartion to be as a decrement one
- left++;
- }
- else
- {
- right++;
- }
- // cout<<ans<<endl;
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement