题目链接：1163. 按字典序排在最后的子串
方法：双指针
解题思路
【正常走路我不走，就是跳，就是玩】
- 任何非后缀子串字典序都小于其相应的后缀子串，如 \(s[i, i + k] < s[i, n - 1]\), \(k < n - 1\)，故答案一定为后缀子串，即 \(s[i, n - 1]\)；
- 观察数据规模，\(4 * 10^5\)，暴力一定超时；
- 法宝：双指针
- 指针 \(i\) ：指向以当前可能为答案的后缀子串的开头；
- 指针 \(j\) ：指向下一个可能为答案的后缀子串的开头；
- 同时给两个指针加上相同的偏移量 \(k\)（每次初始为 \(0\)） ，直到所指向的字符 \(s[i + k] != s[j + k]\)，因为当 \(s[i, i + k] == s[j, j + k]\) 时，由于 \(i\) 在前，答案一定不会是 \(j\) 开头后缀子串；
- \(s[i + k] < s[j + k]\) ，说明 \(s[i, i + k] < s[j, j + k]\)；
- 此时 \([i, i + k]\) 区间的字符一定不会为答案的后缀子串的开头，因为 \(s[i + m, i + k] < s[j + m, j + k]\)，那么就跳过这段非答案数组，\(i += k + 1\)；
- 若此时 \(i >= j\)，即 \([i, i + k + 1]\) 覆盖了 \(j\)，那么应该将 \(j = i + 1\)，指向 \(i\) 的下一个继续比较；
- \(s[i + k] > s[j + k]\)，说明 \(s[i, i + k] > s[j, j + k]\) ；
- 此时 \([j, j + k]\) 区间的字符一定不会为答案的后缀子串的开头，因为 \(s[j + m, j + k] < s[i + m, i + k]\)，那么就跳过这段非答案数组，\(j += k + 1\)；
代码
class Solution {
public:
string lastSubstring(string s) {
int i = 0, j = 1, n = s.length();
while (j < n) {
int k = 0;
while (j + k < n && s[i + k] == s[j + k]) k ++ ;
if (j + k < n && s[i + k] < s[j + k]) {
i += k + 1;
if (i >= j) j = i + 1;
} else {
j += k + 1;
}
}
return s.substr(i);
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。