fork download
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. typedef long long int ll;
  4.  
  5.  
  6. using namespace std;
  7.  
  8. vector<pair<char,ll>> maxi(vector<pair<char,ll>> a , vector<pair<char,ll>> b){
  9.  
  10. int n1 = a.size();
  11. int n2 = b.size();
  12. int n = min(n1,n2);
  13. for(int i=0;i<n;i++){
  14. if(a[i].first > b[i].first){
  15. return a;
  16. }
  17. else if(a[i].first<b[i].first){
  18. return b;
  19. }
  20. else{
  21. if(a[i].second>b[i].second){
  22. return a;
  23. }
  24. else if(a[i].second<b[i].second){
  25. return b;
  26. }
  27. }
  28. }
  29. if(n1>n2){
  30. return a;
  31. }
  32. return b;
  33.  
  34. }
  35. vector<pair<char,ll>> dfs(string &s,ll l , ll r){
  36. int n = s.size();
  37. char max_element='a';
  38.  
  39. for(int i=l;i<=r;i++){
  40. max_element=max(max_element,s[i]);
  41. }
  42. vector<ll> max_element_occurence;
  43.  
  44. for(int i=l;i<=r;i++){
  45. if(s[i]==max_element){
  46. max_element_occurence.push_back((ll)i);
  47. }
  48. }
  49.  
  50. int size = max_element_occurence.size();
  51. vector<pair<char,ll>> temp;
  52.  
  53. if(l<=max_element_occurence[0]-1){
  54. temp = dfs(s,l,max_element_occurence[0]-1);
  55. }
  56.  
  57. for(int i=0;i<size-1;i++){
  58. ll l1 = max_element_occurence[i]+1;
  59. ll r1 = max_element_occurence[i+1]-1;
  60. if(l1<=r1){
  61. temp = maxi(temp,dfs(s,l1,r1));
  62. }
  63. }
  64.  
  65. if(r>=max_element_occurence[size-1]+1){
  66. temp = maxi(temp,dfs(s,max_element_occurence[size-1]+1,r));
  67. }
  68.  
  69. temp.insert(temp.begin(),{max_element,size});
  70. return temp;
  71.  
  72.  
  73. }
  74. int main() {
  75. // your code goes here
  76. string s;
  77. cin>>s;
  78. ll n = s.size();
  79.  
  80. vector<pair<char,ll>> arr=dfs(s,0,n-1);
  81. string ans="";
  82.  
  83. for(int i=0;i<arr.size();i++){
  84. int a = arr[i].second;
  85. for(int j=0;j<a;j++){
  86. ans=ans+arr[i].first;
  87. }
  88. }
  89.  
  90. cout<<ans<<endl;
  91.  
  92.  
  93.  
  94. return 0;
  95. }
Success #stdin #stdout 0s 544KB
stdin
bbzbaza
stdout
zzbb