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

题目链接：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)\)。