作者推荐
本文涉及知识点
字符串 字典序 分类讨论
本题无法使用KMP，因为t1不段变化。
LeetCode1163. 按字典序排在最后的子串
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入：s = “abab”
输出：“bab”
解释：我们可以找出 7 个子串 [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]。按字典序排在最后的子串是 “bab”。
示例 2：
输入：s = “leetcode”
输出：“tcode”
提示：
1 <= s.length <= 4 * 10
s 仅含有小写英文字符。
KMP
令s[0,i)的最后子串是t1，s[0,i]的最后子串t2。则t2一定以s[i]，结尾，因为t1+s[i]一定在t1后面。
{ 从 t 1 取 0 个字符， t 2 = s [ i ] s [ i ] > t [ 0 ] 从 t 1 取后 m 个字符 t [ i − m , i ) + s [ i ] 条件下面详述 \begin{cases} 从t1取0个字符，t2 = s[i] & s[i] > t[0] \\ 从t1取后m个字符 t[i-m,i)+s[i] &条件下面详述\\ \end{cases} {从t1取0个字符，t2=s[i]从t1取后m个字符t[i−m,i)+s[i]s[i]>t[0]条件下面详述
t1[0,m) 不会小于 t[i-m,i)，否则t1就是t[n-m,m)。
如果两种是大于关系，则t1[0,m]大于 t[i-m,i)+s[i] ,不成立。
故一定是相等关系，且t1[m]小于s[i]。
可以利用KMP的公共前后缀。
如果以上情况都不符合，则t2 = t1 + s[i]。
如果使用KMP,t1不断变化，时间复杂度是O(nn)，超时。
分类讨论
令n = s.length()。
性质一：令s[x,y)是最后的子串，x ∈ \in ∈[0,n)则y=n。因为s[x,n)的字典序比s[x,y)大。
性质二:令s[i,n)在s[x,n)中的字典序最大，x ∈ \in ∈[0,j)。确保:j > i。
令s[i,i+k)和s[j,j+k)相等,下标 j+K非法， s[i+k]!=s[j+k]。初始：i=0,j=1,k=0
{ k + + s [ i + k ] = = s [ j + k ] k = 0 , i = j , j + + s [ i + k ] < s [ j + k ] 待证明一 k = 0 , i + = k + 1 s [ i + k ] > s [ j + k ] 待证明二 \begin{cases} k++ & s[i+k]==s[j+k] \\ k=0,i=j,j++& s[i+k] < s[j+k] & 待证明一\\ k=0,i+= k+1 & s[i+k] > s[j+k] & 待证明二\\ \end{cases} ⎩ ⎨ ⎧k++k=0,i=j,j++k=0,i+=k+1s[i+k]==s[j+k]s[i+k]<s[j+k]s[i+k]>s[j+k]待证明一待证明二
待证明一
显然s[j,n)的字典序大于s[i,n)结合性质二，s[j,n)是 s[x,n)中的最大字典序，x ∈ \in ∈[0,j+1)。
待证明二
令x ∈ \in ∈[j,j+k] ，则len = x - j+1 。
s[x,n)的字典序小于s[i+len,n)，结合性质二,s[i+len,n)小于s[i],s[x,n)小于s[i,n)。现在来证明无后效性：
从小到处理len，则:
s[0,j+len)符合性质二，由于s[0,i+len]符合性质二。
超时
多余n-1个a，后面跟一个b。时间复杂度O(nn)。
代码
核心代码
class Solution {
public:
string lastSubstring(string s) {
int i = 0;
for (int j = 1; j < s.length(); )
{
int k = 0;
for (; ((j + k) < s.length()) && (s[j + k] == s[i + k]); k++);
int tmp = i;
if (s[i + k] < s[j + k])
{
i = j++;
}
else
{
j += k + 1;
}
}
return s.substr(i);
}
};
测试用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s ;
{
Solution sln;
s = "cacacb";
auto res = sln.lastSubstring(s);
Assert("cb", res);
}
{
Solution sln;
s = "abab";
auto res = sln.lastSubstring(s);
Assert("bab", res);
}
{
Solution sln;
s = "leetcode";
auto res = sln.lastSubstring(s);
Assert("tcode", res);
}
}
优化
极端情况下，i=j++，执行了n次,k也为n。故时间复杂度为O(nn)。
分两种情况：
一，i+k <= j 不变。
二，i+k > j。下面具体分析：
令m = j-i。
将s[j,j+k)和s[i,i+k)分成若干块,最后一块长度为k%m,前面的块长度都为m，则：
s[j,j+k)的各块分别为：s[j,i) s[i,i+m) s[i+m,i+m2) ⋯ \cdots ⋯
s[i,i+k)的个块分别为：s[i,i+m) s[i+m,i+m2) ⋯ \cdots ⋯
→ \rightarrow → s[j,i) == s [i,i+m) == s[i+m,i+m*2) ⋯ \cdots ⋯
显然s[j,n)淘汰了s[i,n)
x$\in[0,m)
s[j,n)能够淘汰s[j+n,n) 因为s[i,n)删除前m个字符，s[i+x,n)删除就是两者。
同理：s[j+m,n)能淘汰s[j]和s[j+m+x,n)。
⋮ \vdots ⋮
故 i =j + k - (k%m) ⟺ \iff ⟺ i+m+k - (k%m)
因为 m > k%m ，所以 i+m+k - (k%m) > i+ k，也就i至少增加k。
无论什么情况：
i或j至少有一个至少增加k，故总时间复杂度是O(n)。
代码
class Solution {
public:
string lastSubstring(string s) {
int i = 0;
for (int j = 1; j < s.length(); )
{
int k = 0;
for (; ((j + k) < s.length()) && (s[j + k] == s[i + k]); k++);
int tmp = i;
if (s[i + k] < s[j + k])
{
const int m = j - i;
if (k > m)
{
i = (j + k - k%m);
j = i + 1;
}
else
{
i = j++;
}
}
else
{
j += k + 1;
}
}
return s.substr(i);
}
};
2023年5月版
class Solution {
public:
string lastSubstring(string s) {
int iMaxIndex = 0;
for (int i = 1; i < s.length(); i++)
{
int k = 0;
for (; (i + k < s.length()) && (s[i + k] == s[iMaxIndex + k]); k++)
{
}
if ((i + k < s.length()) && (s[i + k] > s[iMaxIndex + k]))
{
auto tmp = iMaxIndex;
iMaxIndex = i;
i = max(i,tmp+k);
}
else
{
i = i + k ;
}
}
return s.substr(iMaxIndex);
}
};
2024年2月版
class Solution {
public:
string lastSubstring(string s) {
int i = 0;
for (int j = 1; j < s.length(); )
{
int k = 0;
for (; ((j + k) < s.length()) && (s[j + k] == s[i + k]); k++);
int tmp = i;
if (s[i + k] < s[j + k])
{
const int m = j - i;
if (k > m)
{
i += k+1;
j = i + 1;
}
else
{
i = j++;
}
}
else
{
j += k + 1;
}
}
return s.substr(i);
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。