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

Categories:

题目描述
思路分析
1. 解法一：双指针比较最大后缀（推荐）
相似题目

题目描述

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

思路分析

解法一：双指针比较最大后缀（推荐）

核心思路：

维护两个起点 i、j，并比较从其开始的后缀。

若 s[i+k] < s[j+k]，说明 i 不可能是答案，跳到 j。

否则移动 j 到 j+k+1 继续比较。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

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 = j;
                j = i + 1;
                k = 0;
            } else {
                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 = j
            j = i + 1
            k = 0
        } else {
            j = j + k + 1
            k = 0
        }
    }
    return s[i:]
}

相似题目

题目	难度	考察点
521. 最长特殊序列 I	简单	字符串
522. 最长特殊序列 II	中等	字符串
1392. 最长快乐前缀	困难	字符串
1163. 按字典序排在最后的子串	困难	双指针
1044. 最长重复子串	困难	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/52879251