题目大意：
按字典序排在最后的子串
给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入："abab" 输出："bab" 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：
输入："leetcode" 输出："tcode"
示：
1 <= s.length <= 4 * 10^5- s 仅含有小写英文字符。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1163
解题思路分析：
题目要求找出字典顺序最大的子字符串，简单说下我的思路吧。首先应该想到，字典顺序最大的字符串的起始位置不能确定，但终点位置一定是字符串的末尾。也就是说这个最大的子字符串不会出现在字符串的中间位置。证明这一点很简单，因为对于任意一个位于元字符串中间的子串，其字典顺序一定小于该子串开头到元字符串末尾的子串，比如：字符串: “azzab”，中间的”zz”是相对较大的子串，但字典顺序中一定小于”zzab”。
接下来我们需要先找出最大的字符，然后将整个字符串按照该最大字符进行分割，如果出现连续的最大字符时则不能分割。举个例子，比如字符串”azzczbzc”，分割后应为：
a zzc zb zc
分割后所有子串中字典顺序最大的一个(zzc)即是返回结果的开头，再加上该子串到原字符串末尾的部分即是返回结果(“zzc+zbzc”)。
实现代码：
public String lastSubstring(String s) {
char[] arr=s.toCharArray(); // 将字符串转为数组
char maxChar=arr[0]; // 找到最大字符
int firstMaxCharIndex=0; // 第一个最大字符所在位置
for(int i=1;i<s.length();i++){
if(arr[i]>maxChar){
maxChar=arr[i];
firstMaxCharIndex=i;
}
}
String max=""; // 以最大字符分割的子串
StringBuilder sb=new StringBuilder(); // 当前子串
// 从第一个最大字符所在位置开始循环
for(int i=firstMaxCharIndex;i<s.length();i++){
// 如果当前字符是最大字符，该字符前的部分是可以被分割的
if(arr[i]==maxChar){
// 该字符前的部分大于最大子串（字典顺序）
if(sb.toString().compareTo(max)>0){
// 更新最大子串
max=sb.toString();
}
// 分割后清空当前子串
sb=new StringBuilder();
// 合并连续的最大字符
for(int j=i;j<s.length();j++){
if(arr[j]!=maxChar) break;
sb.append(maxChar);
i=j;
}
}else{
// 当前字符不是最大字符
// 将当前字符合并到当前子串
sb.append(arr[i]);
}
}
// 循环结束后将最后一部分未分割部分与最大子串比较
if(sb.toString().compareTo(max)>0){
max=sb.toString();
}
// 找到最大子串的开头位置
int index = s.indexOf(max);
// 截取并返回
return s.substring(index);
} 本题解法执行时间为23ms。
Runtime: 23 ms, faster than 29.42% of Java online submissions for Last Substring in Lexicographical Order.
Memory Usage: 43.2 MB, less than 100.00% of Java online submissions for Last Substring in Lexicographical Order.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1163-last-substring-in-lexicographical-order-解题思路分析/