1163. Last Substring in Lexicographical Order
Description
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 * 105
s
contains only lowercase English letters.
Solutions
Solution 1: Two pointers
We notice that if a substring starts from position $i$, then the largest substring with the largest dictionary order must be $s[i,..n-1]$, which is the longest suffix starting from position $i$. Therefore, we only need to find the largest suffix substring.
We use two pointers $i$ and $j$, where pointer $i$ points to the starting position of the current largest substring with the largest dictionary order, and pointer $j$ points to the starting position of the current substring being considered. In addition, we use a variable $k$ to record the current position being compared. Initially, $i = 0$, $j=1$, $k=0$.
Each time, we compare $s[i+k]$ and $s[j+k]$:
If $s[i + k] = s[j + k]$, it means that $s[i,..i+k]$ and $s[j,..j+k]$ are the same, and we add $k$ by $1$ and continue to compare $s[i+k]$ and $s[j+k]$;
If $s[i + k] \lt s[j + k]$, it means that the dictionary order of $s[j,..j+k]$ is larger. At this time, we update $i = i + k + 1$, and reset $k$ to $0$. If $i \geq j$ at this time, we update pointer $j$ to $i + 1$, that is, $j = i + 1$. Here we skip all suffix substrings with $s[i,..,i+k]$ as the starting position, because their dictionary orders are smaller than the suffix substrings with $s[j,..,j+k]$ as the starting position.
Similarly, if $s[i + k] \gt s[j + k]$, it means that the dictionary order of $s[i,..,i+k]$ is larger. At this time, we update $j = j + k + 1$ and reset $k$ to $0$. Here we skip all suffix substrings with $s[j,..,j+k]$ as the starting position, because their dictionary orders are smaller than the suffix substrings with $s[i,..,i+k]$ as the starting position.
Finally, we return the suffix substring starting from $i$, that is, $s[i,..,n-1]$.
The time complexity is $O(n)$, where $n$ is the length of string $s$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|