LeetCode-in-Java
1163. Last Substring in Lexicographical Order
Hard
Given a string s, return the last substring of s in lexicographical order.
Example 1:
Input: s = “abab”
Output: “bab”
Explanation: The substrings are [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]. The lexicographically maximum substring is “bab”.
Example 2:
Input: s = “leetcode”
Output: “tcode”
Constraints:
1 <= s.length <= 4 * 105scontains only lowercase English letters.
Solution
public class Solution {
public String lastSubstring(String s) {
int i = 0;
int j = 1;
int k = 0;
int n = s.length();
char[] ca = s.toCharArray();
while (j + k < n) {
if (ca[i + k] == ca[j + k]) {
k++;
} else if (ca[i + k] > ca[j + k]) {
j = j + k + 1;
k = 0;
} else {
i = Math.max(i + k + 1, j);
j = i + 1;
k = 0;
}
}
return s.substring(i);
}
}