难度: Hard
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入：s = "abab" 输出："bab" 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：
输入：s = "leetcode" 输出："tcode"
提示：
1 <= s.length <= 4 * 105s仅含有小写英文字符。
Submission
运行时间: 198 ms
内存: 18.4 MB
class Solution:
def lastSubstring(self, s: str) -> str:
i,j,k=0,1,0
n=len(s)
while j+k < n:
if s[i+k]==s[j+k]:
k+=1
continue
elif s[i+k]<s[j+k]:
i+=k+1
k=0
if i<j:
i=j
j=i+1
else:
j+=k+1
k=0
return s[i:]
Explain
此题解采用了一种高效的字符串比较策略，目标是找到按字典序排在最后的子串。算法使用两个指针i和j，以及一个偏移量k。指针i始终指向当前认为可能是最大字典序子串的起始位置，而j则用来探索其他可能的起始位置。通过比较s[i+k]与s[j+k]，算法决定如何移动i或j：若s[i+k]小于s[j+k]，则更新i到当前j的位置，因为从j开始的子串具有更大的字典序。若s[i+k]大于s[j+k]，则j向后移动，因为i处的子串仍然是潜在的最大字典序子串。整个过程一直进行，直到j+k等于字符串长度n，此时i处的子串就是所求的最大字典序子串。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def lastSubstring(self, s: str) -> str:
i, j, k = 0, 1, 0 # 初始化指针i, j和偏移量k
n = len(s) # 字符串的长度
while j + k < n: # 当j+k小于字符串长度时循环
if s[i+k] == s[j+k]: # 当前对应字符相同，增加偏移量k
k += 1
continue
elif s[i+k] < s[j+k]: # s[i+k]小于s[j+k]，更新i
i += k + 1
k = 0
if i < j: # 确保i不会超过j
i = j
j = i + 1 # 移动j到i之后
else: # s[i+k]大于s[j+k]，移动j
j += k + 1
k = 0
return s[i:] # 返回从i开始的子串，即最大字典序的子串
Explore
当s[i+k]小于s[j+k]时，说明从位置j开始的子串具有更大的字典序。因此，将i更新到j的位置而不是j+k，是为了重新开始比较从j开始的新子串与当前已知的最大字典序子串。如果更新至j+k，则会跳过j到j+k之间的所有潜在的最大字典序子串的起始位置。这种更新确保了算法不会遗漏可能的最大字典序子串，从而保持算法的正确性。
当s[i+k]和s[j+k]相等时，增加偏移量k可以继续比较后续的字符，以确定哪个子串具有更大的字典序。如果直接移动i或j，将无法比较完整的子串，可能会错过更高字典序的子串。通过增加k，可以在不丢失当前比较基准的情况下，细致地比较两个子串，这增加了算法的精确度和准确性。
当i为j-1时，并且需要更新i到j的位置，实际上i和j已经非常接近，指向连续的两个字符。在这种情况下，更新i到j之后，j会被设置到i+1，即新的i位置的下一个位置。这避免了i和j重叠，保证了j始终在探索新的潜在最大字典序子串的起始位置。
在所有字符都相同的字符串情况下，算法效率确实较低。因为s[i+k]和s[j+k]始终相等，导致偏移量k不断增加直到j+k达到字符串的末尾。这种情况下，算法的时间复杂度接近O(n^2)，因为每次对比都是在逐渐增加k，直到整个字符串结束。这样的线性比较在字符完全相同的情况下会导致效率低下。