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.
Explanation
Consider the following cases:
Input: zyxbzyxa
Expected output: zyxbzyxa
Input: zyxbzyxc
Expected output: zyxc
We have two index pointers, i
and j
. i
will always be set to the index of the final substring result. j
is a moving lookahead index pointer that is used to loop through and compare the character at j
with the character at i
.
When s[i]
and s[j]
are the same (the first z and the second z in the above example), we need to compare the characters next to them (the first y and the second y). Since they are the same, we need to compare the characters next to them (the first x and the second x), and so on. To achieve this, we use an offset k
to compare the k
character next to i
and j
. Note that k
starts at 0, and this is essentially comparing characters s[i+k]
and s[j+k]
.
When s[i+k]
is bigger than s[j+k]
, we just need to let i
remain as is, continue move j
forward to the next character at j+k+1
, and reset k
back to 0.
When s[i+k]
is smaller than s[j+k]
, this means that the substring starting at j
is a better result than the substring at i
. At this point, there are two situations to consider:
When
j
is more thani+k
: Consider an inputhhhccchhhddd
, wheni
is 0,j
is 6, andk
is 3, bothi
andj
are pointing toh
, and you are comparing the firstc
and the firstd
. You would want to seti = j
.When
j
is less thani+k
: Consider an inputnnnp
, wheni
is 0,j
is 1, andk
is 2, you are comparing the lastn
andp
. You would want to changei
to point top
, so you need to seti = i+k+1
. Note that in this case, even thoughj
is equal toi+1
,j
is not always equal toi+1
(see situation 1 above), and hence you should not usei = j+k
.
So with the above considerations, when s[i+k]
is smaller than s[j+k]
, we can simply set i = Math.max(i + k + 1, j)
.
In the end, the result would be the substring starting at i
.
class Solution {
public String lastSubstring(String str) {
int i = 0; // index of final substring.
int j = 1; // index of lookahead possible substring.
int k = 0; // moving offset to compare i & j.
while (j + k < str.length()) {
if (str.charAt(i + k) < str.charAt(j + k)) {
i = Math.max(i + k + 1, j);
j = i + 1;
k = 0;
} else if (str.charAt(i + k) > str.charAt(j + k)) {
j = j + k + 1;
k = 0;
} else {
k += 1;
}
}
return str.substring(i);
}
}
Last updated