---

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

• 标签：双指针、字符串
• 难度：困难

题目链接

• 1163. 按字典序排在最后的子串 - 力扣

题目大意

描述：给定一个字符串 $s$。

要求：找出它所有子串中，按字典序排在最后的那一个子串。

字典序可以简单理解为按字母表先后顺序。比如 "bab" > "aba" > "ab"。

说明：

• $1 \le s.length \le 4 \times 10^{5}$。
• $s$ 仅含小写英文字母。

示例：

输入：s = "abab"
输出："bab"
解释：所有子串中 "bab" 的字典序最大。

解题思路

思路 1：双指针

一个关键观察： 字典序最大的子串一定是原字符串的某个后缀（从某个位置到末尾）。为什么呢？因为如果有一个子串不是后缀，那在这个子串后面加更多字符，只会让字典序变得更大（只要加的不是超小的字符），所以完整的后缀一定大于它的任何前缀子串。

所以问题简化为：找到字典序最大的后缀。

怎么找？

直接比较所有后缀需要 $O(n^2)$ 时间，对于长度 $4\times 10^5$ 的字符串太慢了。用双指针可以做到 $O(n)$。

双指针技巧就像两个候选人竞选「最大后缀」：

• 指针 $i$：当前候选的最大后缀的起始位置。
• 指针 $j$：候选者，要去挑战 $i$。
• 指针 $k$：用来逐字符比较两个候选后缀。

步骤拆解：

1. 初始化 $i = 0$（第一个候选），$j = 1$（挑战者），$k = 0$（比较偏移）。

2. 当 $j + k < n$ 时，比较 $s[i+k]$ 和 $s[j+k]$：

   • 如果相等： $k$ 加 1，继续比较下一个字符。
   • 如果 $s[i+k] < s[j+k]$： 说明 $j$ 开头的后缀更大。更新 $i = i + k + 1$（跳过中间不可能胜出的位置），重置 $j$ 和 $k$。
   • 如果 $s[i+k] > s[j+k]$： 说明 $i$ 开头的后缀更大。$j$ 跳过这一段，$j = j + k + 1$，重置 $k$。

3. 最后返回 $s[i:]$。

思路 1：代码

class Solution:
    def lastSubstring(self, s: str) -> str:
        n = len(s)
        i = 0  # 当前最大后缀的起始位置
        j = 1  # 挑战者的起始位置
        k = 0  # 比较时的偏移量
        
        while j + k < n:
            if s[i + k] == s[j + k]:
                k += 1  # 字符相同，继续往后比
            elif s[i + k] < s[j + k]:
                # j 的后缀更大，更新 i，跳过中间不可能胜出的位置
                i = i + k + 1
                if i >= j:
                    j = i + 1
                k = 0
            else:
                # i 的后缀仍然最大，挑战者往后移动
                j = j + k + 1
                k = 0
        
        return s[i:]

思路 1：复杂度分析

• 时间复杂度：$O(n)$。虽然看着有三层循环，但 $i$、$j$、$k$ 的总移动次数不超过 $n$ 的线性倍。
• 空间复杂度：$O(1)$。只用了几个固定变量（不包含返回结果的空间）。