给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
- 1 <=
s.length<= 4 * \(10^5\) s仅含有小写英文字符。
最关键的是处理时间复杂度，怎么让他小于\(O(n^2)\)。
双指针法：
/**
* @param {string} s
* @return {string}
*/
var lastSubstring = function (s) {
let i = 0;
let j = 1;
let offset = 0;
while (j + offset < s.length) {
if (s[i + offset] === s[j + offset]) {
offset++;
}
else if (s[i + offset] > s[j + offset]) {
j = j + offset + 1;
offset = 0;
} else {
i = i + offset + 1;
offset = 0;
if (i >= j) {
j = i + 1;
}
}
}
return s.slice(i);
};
分析：
首先我们得清楚：最大字典序的子串一定是后缀子串。
比较两个个子串的字典序是从第一个字符往后比较的，也就是比较他们的前缀。
我们从前往后遍历字符串，设置一个指针i指向当前前缀首字符，一个指针j往后面寻找比指针i指向的前缀大的前缀首字符位置。这个寻找过程也就是比较过程。
该过程会遇到三种情况。
✨1.s[i+offset]===s[j+offset]
相等，我们继续完后寻找，offset++。
✨2.s[i+offset]<s[j+offset]
小于，就不是我们需要的元素，j→j+offset+1，offset→0。往后重新开始选取。
✨3.s[i+offset]>s[j+offset]
大于?，我们找到了比指针i指向的前缀大的前缀（从j到j+offset），也就是说指针i指向的前缀（从i到i+offset）可以被忽略了，咱们继续往后面找，i→i+offset+1，offste→0。i如果大于了j，那么j→i+1，因为j的目的是在i的后面找到比i指向的前缀大的前缀。如果找到了最后（j+offset>s.length）都没有找到这样的前缀，那么此时i指向的前缀对应的后缀子串（s.slice(i)）就是我们要寻找的最大字典序的子串。