1163 Last Substring in Lexicographical Order 按字典序排在最后的子串

Description:
Given a string s, return the last substring of s in lexicographical order.

Example:

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 * 10^5
s contains only lowercase English letters.

题目描述:
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 :

示例 1：

输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2：

输入：s = "leetcode"
输出："tcode"

提示:

1 <= s.length <= 4 * 10^5
s 仅含有小写英文字符。

思路:

后缀数组
最大子字符串一定是以最大字符开头的直到字符串结尾的子串
先从后往前找到最大字符第一次出现的位置
然后找到每一个最大字符判断是否需要更新
更新可以直接比较两个待选子串的大小
时间复杂度为 O(n), 空间复杂度为 O(1)

代码:
C++:

class Solution 
{
public:
    string lastSubstring(string s) 
    {
        int n = s.size(), pos = n - 1, max_value = s.back();
        for (int i = n - 2; i > -1; i--) if (s[i] >= max_value) pos = i, max_value = s[i];
        int start = pos + 1, left, right;
        while (start < n) 
        {
            if (s[start] != max_value) ++start;
            else 
            {
                left = pos + 1;
                right = start + 1;
                while (left < start and right < n) 
                {
                    if (s[left] == s[right])
                    {
                        ++left;
                        ++right;
                    }
                    else 
                    {
                        if (s[left] < s[right]) pos = start;
                        start = right;
                        break;
                    } 
                }
                if (left == start or right == n) start = right;
            }
        }
        return s.substr(pos);
    }
};

Java:

class Solution {
    public String lastSubstring(String s) {
        int n = s.length(), pos = n - 1, max = s.charAt(pos);
        for (int i = n - 2; i > -1; i--) {
            if (s.charAt(i) >= max) {
                pos = i;
                max = s.charAt(i);
            }
        }
        int start = pos + 1, left = 0, right = 0;
        while (start < n) {
            if (s.charAt(start) != max) ++start;
            else {
                left = pos + 1;
                right = start + 1;
                while (left < start && right < n) {
                    if (s.charAt(left) == s.charAt(right)) {
                        ++left; 
                        ++right;
                    } else {
                        if (s.charAt(left) < s.charAt(right)) pos = start;
                        start = right;
                        break;
                    } 
                }
                if (left == start || right == n) start = right;
            }
        }
        return s.substring(pos);
    }
}

Python:

class Solution:
    def lastSubstring(self, s: str) -> str:
        n, result = len(s), ""
        for i in range(n):
            result = max(result, s[i:])
        return result