Comment on page

1163.Last-Substring-in-Lexicographical-Order

1163. Last Substring in Lexicographical Order

题目地址

题目描述

Given a string s, return the last substring of s in lexicographical order.
​
Example 1:
Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".
​
Example 2:
Input: "leetcode"
Output: "tcode"
​
Note:
1 <= s.length <= 4 * 10^5
s contains only lowercase English letters.

代码

Approach #1 Two Pointers + offset

class Solution {
public String lastSubstring(String s) {
int n = s.length();
int i = 0, j = 1, offset = 0;
while (i < n && j < n) {
if (i + offset >= n || j + offset >= n) break;
​
if (s.charAt(i + offset) == s.charAt(j + offset)) {
offset++;
} else {
if (s.charAt(i + offset) < s.charAt(j + offset)) {
i = Math.max(i + offset + 1, j + 1);
} else {
j = Math.max(j + offset + 1, i + 1);
}
​
offset = 0;
}
}
​
int l = Math.min(i, j);
return s.substring(l);
}
}

Approach #2

public String lastSubstring(String s) {
int i = 0, j = 1, offset = 0, len = s.length();
while (i + offset < len && j + offset < len) {
char c = s.charAt(i + offset), d = s.charAt(j + offset);
if (c == d) {
++offset;
} else {
// chars in [i, ..., i + offset] <= charAt(i) == charAt(j)
if (c < d) {
i = i + offset + 1;
}
// c > d, chars in [j, ..., j + offset] <= charAt(i) == charAt(j)
else {
j = j + offset + 1;
}
​
// avoid duplicate start indices.
if (i == j) {
++i;
}
​
offset = 0; // reset offset to 0.
}
}
return s.substring(Math.min(i, j));
}