Hard

题目描述

给定一个字符串 s，返回字典序最大的子字符串。

示例 1：

输入：s = "abab"
输出："bab"
解释：子字符串有 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。字典序最大的子字符串是 "bab"。

示例 2：

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

约束条件：

  • 1 <= s.length <= 4 * 10^5
  • s 仅包含小写英文字母。

提示：

  • 假设答案是从索引 i 到 j 的子字符串。如果你加上索引 j+1 处的字符，你会得到更好的答案。
  • 答案总是给定字符串的一个后缀。
  • 由于限制很高，我们需要一个高效的数据结构。
  • 使用后缀数组。

解题思路

解题思路

这道题要求找到字典序最大的子字符串。根据题目提示，答案总是原字符串的一个后缀，这是关键洞察。

方法一：双指针优化

最直观的想法是比较所有后缀，但直接比较会超时。我们可以用双指针优化：

  1. 维护当前最优后缀的起始位置 i
  2. 用指针 j 遍历其他可能的起始位置
  3. 当发现更大的字符时，更新 i；相等时需要继续比较后续字符

方法二：后缀数组（推荐）

使用后缀数组可以在 O(n log n) 时间内解决：

  1. 构建所有后缀的数组
  2. 对后缀进行排序
  3. 返回字典序最大的后缀

但考虑到字符串长度限制，双指针方法在实践中更简洁高效。

核心优化：当比较两个后缀时，如果前缀相同，可以跳过相同的部分，避免重复比较。

代码实现

class Solution {
public:
    string lastSubstring(string s) {
        int n = s.length();
        int i = 0, j = 1, k = 0;
        
        while (j + k < n) {
            if (s[i + k] == s[j + k]) {
                k++;
            } else if (s[i + k] < s[j + k]) {
                i = j;
                j = i + 1;
                k = 0;
            } else {
                j = j + k + 1;
                k = 0;
            }
        }
        
        return s.substr(i);
    }
};

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

public class Solution {
    public string LastSubstring(string s) {
        int n = s.Length;
        int i = 0, j = 1, k = 0;
        
        while (j + k < n) {
            if (s[i + k] == s[j + k]) {
                k++;
            } else if (s[i + k] < s[j + k]) {
                i = j;
                j = i + 1;
                k = 0;
            } else {
                j = j + k + 1;
                k = 0;
            }
        }
        
        return s.Substring(i);
    }
}

var lastSubstring = function(s) {
    const n = s.length;
    let i = 0, j = 1, k = 0;
    
    while (j + k < n) {
        if (s[i + k]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
双指针优化O(n)O(1)
后缀数组O(n log n)O(n)

推荐解法：双指针优化

  • 时间复杂度最优，平均情况下接近 O(n)
  • 空间复杂度常数级别
  • 实现简洁，易于理解

相关题目