fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. string lastSubstring(string s) {
  6.     int N = s.size(), startIdx = N;
  7.     vector<int> cons(N, 1);
  8.  
  9.     function<bool(int, int)> check;
  10.     check = [&](int fIdx, int sIdx){
  11.         if(sIdx == N) return true;
  12.         if(s[fIdx] != s[sIdx]) return s[fIdx] > s[sIdx]; // x.... > a....
  13.         if(cons[fIdx] == cons[sIdx]){
  14.             return check(fIdx + cons[fIdx], sIdx + cons[sIdx]);
  15.             // xxx + Y && xxx + Z --> compare Y & Z
  16.         }
  17.         if(cons[fIdx] > cons[sIdx]) return true; // xxx.... > xx...
  18.         return false; // xx... < xxx....
  19.     };
  20.  
  21.     for(int idx = N - 2; idx >= 0; --idx) if(s[idx] == s[idx + 1]) cons[idx] += cons[idx + 1];
  22.  
  23.     for(int idx = N - 1; idx >= 0; --idx){
  24.         if(check(idx, startIdx)){
  25.             startIdx = idx;
  26.         }
  27.     }
  28.  
  29.     return s.substr(startIdx);
  30.  
  31. }
  32.  
  33. int main() {
  34. 	cout << lastSubstring("leettcodtte");
  35. 	// cons array for leettcodtte is [1,2,1,2,1,1,1,1,2,1,1]
  36. 	return 0;
  37. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tte
https://ideone.com/hFZwZ8
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!