LeetCode 1163. 按字典序排在最后的子串
题目描述
题意分析
从字符串中选择一个非空连续子串，使它在字典序中最大，返回这个子串本身。字典序先比较第一处不同字符；若一方是另一方的完整前缀，则更长的一方更大。
任意没有延伸到原字符串末尾的子串，都可以保留相同起点继续延长，得到更大的字符串。因此最大子串一定是某个后缀，只需确定最优起始下标，无需枚举所有起止组合。
解法：双指针比较最大后缀
核心思路
[!blue]
用
i < j表示两个待比较的后缀起点，k表示它们已确认相等的前缀长度。比较s[i + k]与s[j + k]：相等就增加k，直到出现第一处不同，或较短的后缀到达字符串末尾。一次失配不仅能淘汰两个起点中的较小者，还能淘汰一段连续起点。假设
s[i + k] < s[j + k]，对任意0 <= t <= k，从i + t和j + t出发的两个后缀仍先匹配k - t个字符，然后在同一对失配字符处由前者落败。因此[i, i + k]内的起点都不可能产生最大后缀。此时令
i = max(i + k + 1, j)：既越过刚证明失败的范围，也不能退回先前已经处理的候选；再令j = i + 1，重新比较两个不同起点。反过来，若当前i的字符更大，同样可淘汰[j, j + k]，只需令j += k + 1，保留i。每次换候选后都把
k清零，因为原来的公共前缀只属于旧的一对起点。两个起点只会向右移动，失配前积累的比较长度转化成了这一轮的批量跳跃，避免重复逐一比较长公共前缀。循环在
j + k到末尾时结束。若j已经越界，说明没有后续候选；若只是匹配到后缀j的末尾，因为i < j，后缀i更长且保留了相同前缀，所以它仍然更大。后面尚未逐个比较的起点，也能沿这段相等关系向前平移到更长的同前缀后缀，直到落回已处理区域，不会产生新的最大者。最终返回从i到串尾的后缀。
解题步骤
- 初始化
i = 0、j = 1、k = 0。- 只要
j + k < n，就比较两个后缀在偏移k处的字符。- 字符相等时继续延长公共前缀；
i一侧较小时，将i跳到max(i + k + 1, j)并重设j = i + 1。j一侧较小时，将j跳到j + k + 1；两种失配处理后都清零k。- 循环结束后返回
s[i..n)。
代码实现
class Solution {
public String lastSubstring(String s) {
int n = s.length();
int i = 0;
int j = 1;
// k 记录两个候选后缀已经确认相等的前缀长度。
int k = 0;
while (j + k < n) {
char a = s.charAt(i + k);
char b = s.charAt(j + k);
if (a == b) {
k++;
} else if (a < b) {
// i 输了，[i, i+k] 的起点都可淘汰。
i = Math.max(i + k + 1, j);
j = i + 1;
k = 0;
} else {
// j 输了，[j, j+k] 的起点同样被连带否定。
j = j + k + 1;
k = 0;
}
}
return s.substring(i);
}
}
func lastSubstring(s string) string {
n := len(s)
// i、j 是候选起点，k 是已经确认相等的前缀长度。
i, j, k := 0, 1, 0
for j+k < n {
a := s[i+k]
b := s[j+k]
if a == b {
k++
} else if a < b {
// i 输了，[i, i+k] 的起点都可淘汰。
if i+k+1 > j {
i = i + k + 1
} else {
i = j
}
j = i + 1
k = 0
} else {
// j 输了，[j, j+k] 的起点同样被连带否定。
j = j + k + 1
k = 0
}
}
return s[i:]
}
复杂度分析
- 时间复杂度：$O(n)$。每次失配前的相等比较，可以归入随后至少同规模的指针前移；最后一段连续匹配至多扫描到串尾。Java 构造返回子串的复制也至多为线性。
- 空间复杂度：搜索辅助空间为 $O(1)$。Java 返回子串另需保存结果内容，Go 返回原字符串的后缀视图。
关键点总结
[!green]
- 先用前缀较短则字典序较小的规则，将所有子串归约为后缀选择。
- 已匹配前缀支持平移后的同一失配结论，所以一次比较能排除连续多个起点。
- 保持两个起点单向前进，每次换候选重新计算公共前缀。
- 较短候选匹配到末尾时，较早开始的长后缀胜出，无需继续读取越界字符。
易错点总结
[!yellow]
- 只挑最大首字符的第一个或最后一个位置，忽略首字符相同时还要继续比较后续内容。
- 失配后只把较小一侧前进一格，会重复比较长前缀，失去线性时间保证。
- 更新
i时不与j取最大值，可能重新使用此前已被处理或淘汰的起点。- 换候选后不清零
k，会把旧后缀的相等结论错误用于新后缀。- 循环只判断
j < n，无法阻止公共前缀增长后偏移位置越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1754. 构造字典序最大的合并字符串 | 中等 | 同样需要比较剩余后缀的字典序，而不只是当前首字符，以决定最优结果。 |
| 555. 分割连接字符串 | 中等 | 原题还允许循环切分与独立翻转每段，本题只在单个固定字符串中选择最大后缀。 |