4-24每日

1163. 按字典序排在最后的子串

==Hard==

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

示例 1：

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

题解

我们注意到，如果一个子串从位置 iii 开始，那么字典序最大的子串一定是 $s[i,..n−1]$，即从位置 $i$ 开始的最长后缀。因此，我们只需要找出字典序最大的后缀子串即可。

我们使用双指针 $i$ 和 $j$，其中指针 $i$ 指向当前字典序最大的子串的起始位置，指针 $j$ 指向当前考虑的子串的起始位置。另外，用一个变量 $k$ 记录当前比较到的位置。初始时 $i=0, j=1, k=0$。

每一次，我们比较 $s[i+k]$ 和 $s[j+k]$：

如果 $s[i+k]=s[j+k]$，说明 $s[i,..i+k]$ 和 $s[j,..j+k]$ 相同，我们将 $k$ 加 1，继续比较 $s[i+k]$ 和 $s[j+k]$；

如果 $s[i+k]<s[j+k]$，说明 $s[j,..j+k]$ 的字典序更大。此时，我们更新 $i=i+k+1$，并将 $k$ 重置为 0。如果此时 $i≥j$，那么我们将指针 $j$ 更新为 $i+1$，即 $j=i+1$。这里我们跳过了以 $s[i,..,i+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[j,..,j+k]$ 为起始位置的后缀子串。

同理，如果 $s[i+k]>s[j+k]$，说明 $s[i,..,i+k]$ 的字典序更大。此时，我们更新 $j=j+k+1$，并将 $k$ 重置为 0。这里我们跳过了以 $s[j,..,j+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[i,..,i+k]$ 为起始位置的后缀子串。

最后，我们返回以 $i$ 为起始位置的后缀子串即可，即 $s[i,..,n−1]$。

https://leetcode.cn/problems/last-substring-in-lexicographical-order/solutions/2242562/python3javacgotypescript-yi-ti-yi-jie-sh-3amj/

class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size();
        int i = 0, j = 1, k = 0;
        
        // 遍历所有可能的子串起始位置 i 和 j
        while (j + k < n) {
            if (s[i + k] == s[j + k]) {     // 如果相同，则继续比较后面的字符
                k++;
                continue;
            } else if (s[i + k] < s[j + k]) { // 如果 s[i + k] < s[j + k]，i 跳到 j+1，k 置为 0
                i += k + 1;
                k = 0;
                if (i >= j) {               // 如果发现 i 已经超过[j,n)了，就更新 j=i+1
                    j = i + 1;
                }
            } else {                        // 如果 s[i + k] > s[j + k]，j 跳到下一个后缀的起始位置 k+1,j
                j += k + 1;                 // 跳到下一个后缀的起点
                k = 0;                      // k 重新置为0
            }
        }
        return s.substr(i);                 // 返回最后一个子串
    }
};