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

2023-07-20 HGNULB 约 8 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

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

题意分析

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

第一个必须做的化简是：答案一定是某个后缀。因为对任意子串 s[l..r]，把它向右延长到串尾得到的 s[l..n-1] 以它为前缀，而字典序中「前缀严格小于把它延长后的串」。所以只要固定了左端点，右端点取到底一定不劣。于是候选集合从 $O(n^2)$ 个子串缩小到 $n$ 个后缀，问题变成「求最大后缀」。

第二个观察给出答案的起点特征：最大后缀一定从全串中最大的那个字符开始。若有多个位置出现该最大字符，就要在这些起点之间继续比较后续字符——这正是难点所在，因为相同字符可能大量重复（例如全 "aaaa...a"），朴素两两比较会退化。

约束里 s 长度上限 $4 \times 10^5$，只含小写字母。这个规模明确排除了 $O(n^2)$ 的逐对比较，也排除了朴素地把 $n$ 个后缀排序（每次比较 $O(n)$，总计 $O(n^2 \log n)$）。它要求一个近似线性的做法。

边界：长度为 1 时答案是整串；全同字符时答案是整串（起点 0 的后缀最长，前缀关系决定它最大）；最大字符只出现一次时答案直接就是从该位置到结尾的后缀。

解法：双指针比较最大后缀

核心思路

暴力枚举 $n$ 个后缀并逐个比较，最坏需要 $O(n^2)$ 次字符访问；"aaaa...a" 会让每次比较都走很远。线性做法的关键是：一次失配不仅能淘汰当前输家，还能淘汰它后面一段起点。

维护 i < j 和偏移 k：i 是当前守擂起点，j 是下一个挑战者，并且已经确认
\[s[i..i+k)=s[j..j+k)\]
循环不变量是：所有小于 j 的起点除 i 外都已有“存在更大后缀”的证据，因此不可能成为答案；k 是当前两候选已确认相等的前缀长度。

比较 s[i+k] 与 s[j+k]：

相等时只令 k++。

若 s[i+k] < s[j+k]，对任意 $0 \le t \le k$，后缀 i+t 与 j+t 先相等 $k-t$ 位，随后仍由同一对失配字符决定前者更小，所以 [i, i+k] 全部可淘汰。第一个仍可能有效的守擂者是 max(i+k+1, j)；若旧 j 落在淘汰区内，它也不能保留。

若 s[i+k] > s[j+k]，同理 [j, j+k] 全部输给对应的更早后缀，令 j += k + 1。

每次失配都重置 k，但之前比较出的 k 个相等字符会立刻转化为至少 k+1 的指针跳跃，不会被无限重复扫描。淘汰都有一个明确更大的后缀作为证据，因此不会删掉真正答案。若循环因 j+k=n 结束，对任意剩余起点 r=j+t，后缀 s[r..] 都是更早后缀 s[i+t..] 的真前缀，仍不可能最大；结合不变量，最终只剩 i，返回 s[i..]。

解题步骤

初始化：i = 0、j = 1、k = 0。守擂者从第一个后缀开始，挑战者紧随其后。长度为 1 的串会因 j + k = 1 = n 直接跳过循环、返回整串，无需特判。

循环条件 j + k < n：越界检查只需盯住 j + k，因为 i < j 保证了 i + k 一定更小、不会越界。这一条同时也是算法的终止依据——挑战者用尽即结束。

取两位比较：a = s[i+k]、b = s[j+k]。比较的是两条后缀在同一相对偏移上的字符，这正是字典序比较的定义。

相等则 k++：延长公共前缀，两个指针都不动。这是唯一「不产生淘汰」的分支，但它推进了 k，为后续两个分支积累跳跃距离。

a < b 时守擂者出局：i = max(i + k + 1, j)。i + k + 1 跳过本轮证明失败的区间，j 则防止退回前几轮已淘汰的位置。随后令 j = i + 1、k = 0。若只写 i = j，在 "aaa...ab" 上会反复比较几乎相同的长前缀，退化为 $O(n^2)$。

a > b 时挑战者出局：j = j + k + 1、k = 0。同样一次跳过 k + 1 个起点。注意这里 i 保持不变，守擂成功。

返回 s.substring(i)：答案是后缀，直接从最优起点截到结尾。

例如 s = "cacacb"：起点 0 与 2 先连续匹配 "cac"，随后比较到 'a' < 'b'，于是 [0,3] 一次淘汰，i = 4；再比较后缀 "cb" 与 "b"，后者落败，返回 "cb"。

边界上，s = "a" 不进入循环，直接返回整串；s = "aaaa" 最终遇到挑战者到达串尾，较短后缀都是较长后缀的真前缀，答案仍是起点 0 的 "aaaa"；s = "aaab" 则一次长公共前缀后跳到最后的 "b"。

代码实现

class Solution {
    public String lastSubstring(String s) {
        int n = s.length();
        int i = 0;
        int j = 1;
        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 := 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)$，其中 $n$ 为字符串长度。每轮循环要么让 k 增加 1，要么把 k 清零同时让 i + j 至少增加 k + 1。由于 i 与 j 都单调不减且上界为 $n$，k 的累计增量不超过 i + j 的总增量，因此比较次数是 $O(n)$ 的摊还常数级。最后 substring 复制答案额外 $O(n)$。

空间复杂度：$O(1)$，只用 i、j、k 三个下标变量；不计返回的子串本身。

关键点总结

「所有子串中字典序最大」先化简成「所有后缀中最大」：任何子串都严格小于把它延长到串尾的版本，这一步把候选从 $O(n^2)$ 降到 $n$，是解题的第一句话。

双指针的三个变量各有确定语义——i 是当前最优、j 是挑战者、k 是已确认的公共前缀长度，三者构成循环不变量，写代码前先把它说清楚。

比较失败时不要只淘汰一个候选：一次长度为 k 的比较能连带否定 k 个起点，把它转化成指针跳跃，才把 $O(n^2)$ 摊还成 $O(n)$。

i = max(i + k + 1, j) 中前一项跳过本轮败者区间，后一项避免回到历史淘汰区；两部分共同维护 i < j 和单调前进。

越界只需检查 j + k，因为 i < j 恒成立；单字符输入由循环条件自然覆盖，不必特判。

面试视角：这题的标准答案就是这个双指针，能讲清「为什么可以跳 k 个」的证明是拿分点。若面试官追问其他做法，可以提后缀数组（构造后取排名最大的后缀，$O(n \log n)$）或后缀自动机，但要说明双指针在本题既更简单又更快。

易错点总结

错误写法：a < b 分支只写 i = j。用例 s = "aaaa...ab"：每轮只淘汰一个起点，却重复扫描长公共前缀，结果虽对但会退化为 $O(n^2)$。

错误写法：i = i + k + 1 而漏掉与 j 取 max。用例 s = "baac"：前两次比较已把 j 推到 3，c 胜出时却把 i 退回 1，重新进入已淘汰区间，破坏单调性与复杂度保证。

错误写法：a > b 分支只写 j++。用例 s = "cbcbca"：起点 0 与 2 匹配 "cbc" 后才分出胜负，本可一次淘汰 [2,5]；逐个推进会反复比较相同前缀并退化为 $O(n^2)$。

错误写法：任一分支忘记把 k 归零。用例 s = "cacacb"：新的一对候选带着旧的公共前缀长度开始比较，s[i+k] 取到的位置与实际公共前缀不符，结果错误。

错误写法：循环条件写成 j < n。用例 s = "aaa"：k 增长后 j + k 已越界，s.charAt(j + k) 抛出越界异常。

错误捷径：只取最大字符第一次或最后一次出现的位置。"cacacb" 的答案从最后一个 c 开始，而 "cbcba" 的答案却从第一个 c 开始；首字符相同后仍要比较完整后缀。

相似题目

题目	难度	考察点
316. 去除重复字母	中等	同为字典序最优化，但用单调栈按贪心逐位构造而非在后缀间挑选
1081. 不同字符的最小子序列	中等	与 316 同题不同表述，方向改为最小，练习字典序比较的方向翻转
1044. 最长重复子串	困难	同样是后缀间的比较问题，用二分长度 + 滚动哈希，可对照后缀数组解法
214. 最短回文串	困难	靠前缀与后缀的匹配关系求解，KMP 的失配指针与本题的跳跃思想同源
28. 找出字符串中第一个匹配项的下标	简单	「利用已比较过的信息避免回退」的入门题，是理解本题跳跃的基础
187. 重复的DNA序列	中等	定长子串的哈希去重，展示另一类避免逐字符重复比较的手段