05 August 2008
给一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入：”abab” 输出：”bab” 解释：我们可以找出 7 个子串 [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]。按字典序排在最后的子串是 “bab”。 示例 2：
输入：”leetcode” 输出：”tcode”
从后往前遍历，遇到更大的字符交换指针。 遇到相同的字符，先不着急比较后续的字符，看看它前面的一个是不是一样的，一样的就continue，直到不一样或者到头了，再比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public String lastSubstring(String s) {
char[] chs = s.toCharArray();
int index = chs.length - 1;
int max = 0;
for (int i = chs.length - 1; i >= 0; i--) {
if (chs[i] - 'a' > max) {
index = i;
max = chs[i] - 'a';
} else if (chs[i] - 'a' == max) {
if (i - 1 >= 0 && chs[i] == chs[i - 1]) continue;//非常关键！！！
int temp = index;
index = i;
max = chs[i] - 'a';
for (int j = i, k = temp; j < chs.length && k < chs.length; j++, k++) {
if (chs[k] - 'a' == chs[j] - 'a') continue;
if (chs[k] - 'a' > chs[j] - 'a') {
index = temp;
max = chs[index] - 'a';
break;
} else if (chs[k] - 'a' < chs[j] - 'a') {
break;
}
}
}
}
return s.substring(index);
}
}