【leetcode】1163. Last Substring in Lexicographical Order
题目的描述：
Given a string s, return the last substring of s in lexicographical order.
Example 1:
Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"].
The lexicographically maximum substring is "bab".
Example 2:
Input: "leetcode"
Output: "tcode"
Note:
1 <= s.length <= 10^5
s contains only lowercase English letters.
理解题目的意思，花了大半天的时间，即使是看了答案，也没有立即清除题目的意思，这个时候，就体现出来英语的重要了。
the last substring of s in lexicographical order
如果一个字符串s,可以给出来这个字符串s包含的所有的子串，代码如下：
public static void main(String[] args) {
System.out.print(allSubString("eetcode"));
}
private static List<String> allSubString(String string) {
List<String> resultList = new ArrayList<String>();
for (int i = 0; i < string.length(); i++) {
for (int j = i+1; j <= string.length(); j++) {
resultList.add(string.substring(i, j));
}
}
return resultList;
}
例如上面的测试用例中的：eetcode，所有的子串就是：
[e, ee, eet, eetc, eetco, eetcod, eetcode,
e, et, etc, etco, etcod, etcode, t, tc, tco,
tcod, tcode, c, co, cod, code, o, od, ode, d, de, e]
这些子串，按照字典排序，那么最后的那个子串就是：tcode
这个问题，就是给出来，一个字符串s,然后给出来这个字符串s，按照字典排序的那个最后的子串。
然后，就是各种的分析，其中首先找到最迟的那个字符，标志着字典序的确认进入了一大步，然后我们就可以直接的从选中的那个字符开始到字符转结束，就是那个”最后的字符串”了。具体的代码为：
public static void main(String[] args) {
System.out.println(allSubString("eetcode"));
System.out.println(lastSubstring("eetcode"));
}
public static String lastSubstring(String str) {
String mx = "";
char cur = 'a';
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) >= cur && mx.compareTo(str.substring(i)) <= 0) { // the first letter of substring matters,
cur = str.charAt(i);
mx = str.substring(i); // for example, "tabc" is lexicographically larger than "tab"
}
while (i != str.length() - 1 && str.charAt(i) == str.charAt(i + 1))
i++; // get rid of continuous repeating letters
}
return mx;
}
仔细分析，这个算法，因为有一个一个substring的操作，所以这个时间的复杂度应该为O(n2)，最坏的情况，就是：ababab…….
这道题目的关键在于i的移动，我们每次比较的时候，动用了
mx.compareTo(str.substring(i)) <= 0
而且我们这样的比较导致了一个O(n),能够按照坐标，上一次开始，到这次的比较的点，进行比较，这样就不需要O(n)，分析到这里，就和一个机制很像了：滑动窗口
具体的代码：
public static String lastSubstring(String s) {
int n = s.length();
// We have two pointers each pointing at the start of a
// possible candidate substring. The pointer on the left
// is the start of the final answer. Move the pointer with
// smaller ASCII value to the right.
// 两个类似指针的标志位，i和j, i 表示最后字段子串的起始位，j为滑动窗口的位置，curLen为窗口的大小
int i = 0, j = 1, curLen = 0;
while (i < n && j < n && curLen < n) {
// 如果窗口的越过了n则直接的结束
if (i + curLen >= n || j + curLen >= n) {
break;
}
// 窗口的开始大小为0，所以扩展的前提是：i和j的下一个字符是一样的，可以直接则增加窗口
if (s.charAt(i + curLen) == s.charAt(j + curLen)) {
curLen++;
} else {
// If two strings have different priority, move the pointer that
// is pointing to the start of the string with lower priority.
// We can directly do i += curLen + 1 instead of i += 1 because
// the substring from i to i + curLen has already been covered
// (it is impossible that any substring in this range will have a
// higher priority than the one that the other pointer is pointing
// to right now). Thus, we can skip them directly
// E.g. d a b d a b x
// i j --> curLen = 3 (dab = dab)
// When curLen = 4, d < x, so we need to move i to the right
// We can move i to index 4 (i.e. the second a) directly. If some
// character between index 1 (the first a) and pointer j has higher
// priority than the character pointed to by j, then i will have left
// i long ago, which is clearly a contradiction.
// 如果位置i的字符的字典序，小于j字符的字典序，i直接的递增curLen + 1
if (s.charAt(i + curLen) < s.charAt(j + curLen)) {
i += curLen + 1;
} else {
j += curLen + 1;
}
if (i == j) {
j++;
}
curLen = 0;
}
}
return s.substring(Math.min(i, j));
}
i和j的移动，就是第一版的优化而来的，并不是特别的依赖某种的算法过来的。