ccbeginner

TNFSH 26

Feb 11th, 2020
109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TNFSH 26
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. vector<int> v[128];
  6. bool cmp(int a, int b){return a > b;}
  7.  
  8. int32_t main(){
  9.     int t;
  10.     string s;
  11.     cin >> t;
  12.     while(t--){
  13.         cin >> s;
  14.         for(int i = 'a'; i <= 'z'; ++i)v[i].clear();
  15.         for(int i = 0; i < s.size(); ++i)v[s[i]].emplace_back(i);
  16.         vector<int> ans;
  17.         for(int i = 0; i < s.size(); ++i){
  18.             for(int j = 0; j < v[s[i]].size(); ++j){
  19.                 if(ans.empty() || v[s[i]][j] < ans.back())ans.emplace_back(v[s[i]][j]);
  20.                 else *lower_bound(ans.begin(), ans.end(), v[s[i]][j], cmp) = v[s[i]][j];
  21.             }
  22.         }
  23.         cout << ans.size() << '\n';
  24.     }
  25.     return 0;
  26. }
RAW Paste Data