jayati

Smallest Window in a string containing all the characters of another string

Sep 26th, 2023
1,631
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. //{ Driver Code Starts
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. // } Driver Code Ends
  7. class Solution
  8. {
  9.     public:
  10.  
  11.     string smallestWindow (string s, string p)
  12.     {
  13.         string str=s;
  14.         string pat=p;
  15.         int no_of_chars=256;
  16.           int len1 = str.length();
  17.     int len2 = pat.length();
  18.  
  19.     if (len1 < len2) {
  20.        
  21.         return "-1";
  22.     }
  23.  
  24.     int hash_pat[no_of_chars] = { 0 };
  25.     int hash_str[no_of_chars] = { 0 };
  26.  
  27.     for (int i = 0; i < len2; i++)
  28.         hash_pat[pat[i]]++;
  29.  
  30.     int start = 0, start_index = -1, min_len = INT_MAX;
  31.  
  32.    
  33.     int count = 0;
  34.     for (int j = 0; j < len1; j++) {
  35.        
  36.  
  37.         hash_str[str[j]]++;
  38.  
  39.         if (hash_str[str[j]] <= hash_pat[str[j]])
  40.             count++;
  41.  
  42.  
  43.         if (count == len2) {
  44.  
  45.             while (hash_str[str[start]]
  46.                        > hash_pat[str[start]]
  47.                    || hash_pat[str[start]] == 0) {
  48.  
  49.                 if (hash_str[str[start]]
  50.                     > hash_pat[str[start]])
  51.                     hash_str[str[start]]--;
  52.                 start++;
  53.             }
  54.  
  55.             int len_window = j - start + 1;
  56.             // cout<<len_window<<endl;
  57.             if (min_len > len_window) {
  58.                 min_len = len_window;
  59.                 start_index = start;
  60.             }
  61.         }
  62.     }
  63.  
  64.     if (start_index == -1) {
  65.        
  66.         return "-1";
  67.     }
  68.  
  69.     return str.substr(start_index, min_len);
  70.     }
  71. };
  72.  
  73. //{ Driver Code Starts.
  74. int main()
  75.  {
  76.     int t;
  77.     cin>>t;
  78.     while(t--)
  79.     {
  80.         string s;
  81.         cin>>s;
  82.         string pat;
  83.         cin>>pat;
  84.         Solution obj;
  85.         cout<<obj.smallestWindow(s, pat)<<endl;
  86.        
  87.     }
  88.     return 0;
  89. }
  90. // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment