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. 1 <= s.length <= 4 * 10^5

2. 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:

1. When j is more than i+k: Consider an input hhhccchhhddd, when i is 0, j is 6, and k is 3, both i and j are pointing to h, and you are comparing the first c and the first d. You would want to set i = j.

2. When j is less than i+k: Consider an input nnnp, when i is 0, j is 1, and k is 2, you are comparing the last n and p. You would want to change i to point to p, so you need to set i = i+k+1. Note that in this case, even though j is equal to i+1, j is not always equal to i+1 (see situation 1 above), and hence you should not use i = 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);
    }
}