代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入：s = "abab" 输出："bab" 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：
输入：s = "leetcode" 输出："tcode"
提示：
1 <= s.length <= 4 * 105s 仅含有小写英文字符。我们注意到，如果一个子串从位置 $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)$。
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:]
class Solution {
public String lastSubstring(String s) {
int n = s.length();
int i = 0;
for (int j = 1, k = 0; j + k < n;) {
int d = s.charAt(i + k) - s.charAt(j + k);
if (d == 0) {
++k;
} else if (d < 0) {
i += k + 1;
k = 0;
if (i >= j) {
j = i + 1;
}
} else {
j += k + 1;
k = 0;
}
}
return s.substring(i);
}
}
class Solution {
public:
string lastSubstring(string s) {
int n = s.size();
int i = 0;
for (int j = 1, k = 0; j + k < n;) {
if (s[i + k] == s[j + k]) {
++k;
} else if (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.substr(i);
}
};
func lastSubstring(s string) string {
i, n := 0, len(s)
for j, k := 1, 0; j+k < n; {
if s[i+k] == s[j+k] {
k++
} else if 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:]
}
function lastSubstring(s: string): string {
const n = s.length;
let i = 0;
for (let j = 1, k = 0; j + k < n; ) {
if (s[i + k] === s[j + k]) {
++k;
} else if (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.slice(i);
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。