What is the best approach for 'Last Substring in Lexicographical Order'?

Use two pointers with invariant tracking, comparing characters incrementally to maintain the current maximal substring.

Can we generate all substrings to solve this problem?

Generating all substrings is inefficient, resulting in O(n^2) time, and is unnecessary with the two-pointer scanning method.

How does the two-pointer invariant work in this problem?

It tracks the current candidate for the maximal substring and skips over any starting indices that cannot produce a larger substring.

What are common mistakes when implementing this solution?

Mistakes include mismanaging pointer updates, incorrectly comparing equal characters, or attempting brute-force substring generation.

Is this approach applicable to variations with digits or uppercase letters?

Yes, the two-pointer scanning with invariant tracking works for any lexicographical order, including uppercase letters or digits.

#1163

Hard

auto_awesome双·指针·invariant

LeetCode 题解工作台

按字典序排在最后的子串

给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。示例 1：输入： s = "abab" 输出： "bab" 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab…

双指针字符串

题目描述

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

示例 1：

输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2：

输入：s = "leetcode"
输出："tcode"

提示：

1 <= s.length <= 4 * 10⁵
s 仅含有小写英文字符。

lightbulb

解题思路

方法一：双指针

我们注意到，如果一个子串从位置 $i$ 开始，那么字典序最大的子串一定是 $s[i,..n-1]$ ，即从位置 $i$ 开始的最长后缀。因此，我们只需要找出字典序最大的后缀子串即可。

我们使用双指针 $i$ 和 $j$ ，其中指针 $i$ 指向当前字典序最大的子串的起始位置，指针 $j$ 指向当前考虑的子串的起始位置。另外，用一个变量 $k$ 记录当前比较到的位置。初始时 $i = 0$ , $j=1$ , $k=0$ 。

每一次，我们比较 $s[i+k]$ 和 $s[j+k]$ ：

如果 $s[i + k] = s[j + k]$ ，说明 $s[i,..i+k]$ 和 $s[j,..j+k]$ 相同，我们将 $k$ 加 $1$ ，继续比较 $s[i+k]$ 和 $s[j+k]$ ；

如果 $s[i + k] \lt s[j + k]$ ，说明 $s[j,..j+k]$ 的字典序更大。此时，我们更新 $i = i + k + 1$ ，并将 $k$ 重置为 $0$ 。如果此时 $i \geq j$ ，那么我们将指针 $j$ 更新为 $i + 1$ ，即 $j = i + 1$ 。这里我们跳过了以 $s[i,..,i+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[j,..,j+k]$ 为起始位置的后缀子串。

同理，如果 $s[i + k] \gt s[j + k]$ ，说明 $s[i,..,i+k]$ 的字典序更大。此时，我们更新 $j = j + k + 1$ ，并将 $k$ 重置为 $0$ 。这里我们跳过了以 $s[j,..,j+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[i,..,i+k]$ 为起始位置的后缀子串。

最后，我们返回以 $i$ 为起始位置的后缀子串即可，即 $s[i,..,n-1]$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def lastSubstring(self, s: str) -> str:
        i, j, k = 0, 1, 0
        while j + k < len(s):
            if s[i + k] == s[j + k]:
                k += 1
            elif s[i + k] < s[j + k]:
                i += k + 1
                k = 0
                if i >= j:
                    j = i + 1
            else:
                j += k + 1
                k = 0
        return s[i:]

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is compared at most twice during the scanning process. Space complexity is O(1) aside from the input string, as only pointers and counters are maintained.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate quickly identifies two-pointer approach.
question_mark
Candidate maintains a clear invariant for substring comparison.
question_mark
Candidate explains skipping non-optimal substrings efficiently.

warning

常见陷阱

外企场景

error
Trying to generate all substrings, leading to O(n^2) time complexity.
error
Not handling equal character comparisons correctly, missing the correct candidate.
error
Resetting pointers incorrectly when a better substring is found, breaking the invariant.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the last substring in lexicographical order for uppercase letters.
arrow_right_alt
Find the last substring when s contains both letters and digits.
arrow_right_alt
Compute the last substring allowing wrap-around comparisons in a circular string.

help

常见问题

外企场景

继续练习

#1147 段式回文 #1048 最长字符串链 #1023 驼峰式匹配