Advertisement
Kali_prasad

enclosing a substring using unordered map

Apr 9th, 2022
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef pair<string,int> psi;
  10. typedef unordered_map<int,int> mii;
  11. typedef unordered_map<long long,long long> mll;
  12. typedef map<string,int> msi;
  13. typedef unordered_map<char,int> mci;
  14. typedef set<int> si;
  15. typedef set<long long> sll;
  16. typedef set<string> ss;
  17. typedef set<char> sc;
  18. typedef vector<int> vi;
  19. typedef vector<string> vs;
  20. typedef vector<char> vc;
  21. typedef vector<ll> vll;
  22. typedef vector<vector<int>> vvi;
  23. typedef vector<vector<string>> vvs;
  24. typedef vector<vector<ll>> vvll;
  25.  
  26. #define FOR(i, a, b) for (auto i=a; i<=(b); i++)
  27. #define FORd(i,b,a) for (int i =b; i >= a; i--)
  28. #define sz(x) (int)(x).size()
  29. #define mp make_pair
  30. #define pb push_back
  31. #define f first
  32. #define s second
  33. #define ins insert
  34.  
  35. const int MOD = 1000000007;
  36. //type functions here
  37. bool check(mci m,mci b)
  38. {
  39.     for(auto x:m)
  40.     {
  41.        // cout<<x.f<<b[x.f]<<endl;
  42.         if(b[x.f]<x.s) return false;
  43.        
  44.     }
  45.     return true;
  46. }
  47.  
  48.  
  49. int main() {
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.     int tc=1;
  53.     cin>>tc;
  54.     FOR(w,1,tc)
  55.     {
  56.         string big="tt0ss00t",small="st";
  57.         cin>>small>>big;
  58.         mci m,b;
  59.        
  60.         for(auto x:small)  m[x]++;
  61.        
  62.        
  63.         int i=0,j=0,sze=sz(big),count=INT_MAX;
  64.         while(i<sze&&j<sze)
  65.         {
  66.            
  67.             while(i<sze&&check(m,b)==false)
  68.             {
  69.                
  70.                 b[big[i]]++;
  71.                 i++;
  72.              
  73.                
  74.             }
  75.          
  76.             while(j<sze&&check(m,b)==true)
  77.             {
  78.                
  79.                 int curr=(i-1)-j+1;
  80.                 if(b[big[j]]==1)  b.erase(big[j]);
  81.                 else              b[big[j]]--;
  82.              
  83.                 j++;
  84.                 count=min(count,curr);
  85.             }
  86.            
  87.         }
  88.         if(count==INT_MAX) cout<<"-1"<<endl;
  89.         else              cout<<count<<endl;
  90.        
  91.     }
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement