[LeetCode] 1163. Last Substring in Lexicographical Order

[grandyang]

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.

这道题给了一个字符串s，让返回其字母顺序最大的一个子串。所谓字母顺序就是字典顺序，按字母表的顺序进行排列，比如 ba 大于 abc，bca 大于 bc，等等。那么为了让字母顺序最大，子串的第一个字母肯定是越大越好，所以若s中不存在重复字母的话，那么只要找最大字母开头的子串就行了，比如 abedc，就知道是 edc 了。但是若存在重复字母，比如 abeced，可以发现 eced 是小于 ed 的，所以就没法直接找到。但是当两个e的位置确定了，就可以一个个的接着往下比较，当后的字母相同时，接续比较下一对，若不同时，则要进行更新，这就是经典的双指针的操作，这里用两个指针i和j，i指向s的第一个字母，j指向第二个字母，用个变量 len 表示当前已经比较的个数。进行循环，条件是 j+len 小于n，若 s[i+len] 等于 s[j+len]，说明对应的字母相等，增加 len 的长度。若 s[i+len] 小于 s[j+len]，说明前面的子串的字母顺序小，此时i更新为 max(i + len + 1, j)，并重置 len 为0。想一想为啥要这么更新呢，当s是 aaaaaab，i=0，j=1 时，可以发现 len 一直可以增加到5，然后出现不同，此时 i+len+1 是要大于j的，可以避免重复比较。而当s是 edcbaf，i=0，j=5，len=0 时，此时j是大于 i+len+1 的，可以避免重复比较。再来看最后一种情况， 若 s[i+len] 大于 s[j+len]，说明此时i开头的子串大，由于j后面的 len 个字母都比较过了，所以此时j加上 len+1，并重置 len 为0。最终返回以i位置开头的子串即为所求，参见代码如下：

class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size(), i = 0, j = 1, len = 0;
        while (j + len < n) {
            if (s[i + len] == s[j + len]) ++len;
            else if (s[i + len] < s[j + len]) {
                i = max(i + len + 1, j);
                j = i + 1;
                len = 0;
            } else {
                j += len + 1;
                len = 0;
            }
        }
        return s.substr(i);
    }
};

Github 同步地址:

#1163

参考资料：

https://leetcode.com/problems/last-substring-in-lexicographical-order/

https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/582703/C%2B%2B-SIMPLE-EASY-SOLUTION-WITH-EXPLANATION-CHEERS!!!

https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/363662/Short-python-code-O(n)-time-and-O(1)-space-with-proof-and-visualization

LeetCode All in One 题目讲解汇总(持续更新中...)