[LeetCode] 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.

按字典序排在最后的子串。

题意是找一个字符串里面所有的子串里面字典序最大的那一个。这个题的本质是在找字典序最大的后缀子串。首先明确一下什么叫字典序的大小。比如字母a和字母b，a的字典序应该比b的字典序小，应该排在前面；如果是aa和ab这种有相同前缀的子串比较，应该是aa的字典序更小，因为第一个不同的字母比较，a比b小，所以aa字典序更小。

按照之前解释的规则，如果要保证字典序最大，那么这个子串开头的字母一定要最大，比如一个开头为z的子串，其字典序一定比一个开头为a的子串更小。其次，这个子串一定不是截取了原字符串中间的部分，而是整个字符串的一个后缀。一个反例（看第二个例子）是如果一个中间的子串是 tc ，那么 tcode 的字典序一定比 tc 更小。

思路是双指针。我们用左指针left找当前最大的字母（字典序最小），用right指针去往后找是否有更大的字母。

使用指针left记录当前最大的后缀子串的起始坐标。指针right用来试探，看后面是否还有字典序更大的字母。一开始left = 0， right = 1，从左往右遍历。
当str[left] < str[right], 则一left开头的后缀子串一定小于以right开头的后缀子串，所以left = right， right + 1
当str[left] > str[right], 则left不动，right + 1
当str[left] 等于 str[right]，则比较str[left + k], str[right + k], k = 1、2、3...。直到出现不相等，否则一直比较直到结束
- 这里的K理解为offset，两个子串都需要加
当str[left + k] 小于 str[right + k]， left = right, right + 1
当str[left + k] 大于 str[right + k]， left不动, right+step + 1

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public String lastSubstring(String s) {
 3         int left = 0;
 4         int right = left + 1;
 5         int step = 0;
 6         while (right + step < s.length()) {
 7             if (s.charAt(left + step) < s.charAt(right + step)) {
 8                 left = right;
 9                 right++;
10                 step = 0;
11             } else if (s.charAt(left + step) == s.charAt(right + step)) {
12                 step++;
13             } else {
14                 right += step + 1;
15                 step = 0;
16             }
17         }
18         return s.substring(left);
19     }
20 }

我这里再提供另一种写法，个人感觉这个写法更直观。还是创建两个指针 i 和 j，j 更靠右边，j 是去寻找潜在的字典序比 i 指向的字母的字典序更大的字母。当两个指针指向的字母相同的时候，直接就是K++；一旦不同，则根据情况变动 i 和 j 指向的位置，同时把K归零。

 1 class Solution {
 2     public String lastSubstring(String s) {
 3         int l = s.length();
 4         int i = 0, j = 1, k = 0;
 5         while (j + k < l) {
 6             if (s.charAt(i + k) == s.charAt(j + k)) {
 7                 k++;
 8                 continue;
 9             }
10             if (s.charAt(i + k) > s.charAt(j + k)) {
11                 j++;
12             } else {
13                 i = j;
14                 j = i + 1;
15             }
16             k = 0;
17         }
18         return s.substring(i);
19     }
20 }

LeetCode 题目总结