# 1163. Last Substring in Lexicographical Order

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: string lastSubstring(string s) { int i = 0; int j = 1; int k = 0; // the number of the same letters of s[i..n) and s[j..n) while (j + k < s.length()) { if (s[i + k] == s[j + k]) { ++k; } else if (s[i + k] > s[j + k]) { // s[i..i + k] == s[j..j + k] and s[i + k] > s[j + k] means that we // should start from s[j + k] to find a possible larger substring. j += k + 1; k = 0; } else { // s[i..i + k] == s[j..j + k] and s[i + k] < s[j + k] means that either // starting from s[i + k + 1] or s[j] has a larger substring. i = max(i + k + 1, j); j = i + 1; k = 0; } } return s.substr(i); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public String lastSubstring(String s) { int i = 0; int j = 1; int k = 0; // the number of the same letters of s[i..n) and s[j..n) while (j + k < s.length()) { if (s.charAt(i + k) == s.charAt(j + k)) { ++k; } else if (s.charAt(i + k) > s.charAt(j + k)) { // s[i..i + k] == s[j..j + k] and s[i + k] > s[j + k] means that we // should start from s[j + k] to find a possible larger substring. j += k + 1; k = 0; } else { // s[i..i + k] == s[j..j + k] and s[i + k] < s[j + k] means that either // starting from s[i + k + 1] or s[j] has a larger substring. i = Math.max(i + k + 1, j); j = i + 1; k = 0; } } return s.substring(i); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def lastSubstring(self, s: str) -> str: i = 0 j = 1 k = 0 # the number of the same letters of s[i..n) and s[j..n) while j + k < len(s): if s[i + k] == s[j + k]: k += 1 elif s[i + k] > s[j + k]: # s[i..i + k] == s[j..j + k] and s[i + k] > s[j + k] means that we # should start from s[j + k] to find a possible larger substring. j += k + 1 k = 0 else: # s[i..i + k] == s[j..j + k] and s[i + k] < s[j + k] means that either # starting from s[i + k + 1] or s[j] has a larger substring i = max(i + k + 1, j) j = i + 1 k = 0 return s[i:]