插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。 
坚持不懈，越努力越幸运，大家一起学习鸭~~~

2哥：3妹，今天周日，有什么打算吗。
3妹：宅在家里呗，外面热死了
2哥：是的，现在全国各地都在高温，今年的天气真是奇怪
3妹：对哦， 还有些地方高温过后又开始内涝
2哥：2022真是不平凡的一年啊，先是疫情，又是高温，又是内涝的
3妹：2哥，你能不能正能量一些，想想开心的事情，比如教我学算法啊

题目：

给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 1：

输入：s = “abab”
输出：“bab”
解释：我们可以找出 7 个子串 [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]。按字典序排在最后的子串是 “bab”。
示例 2：

输入：s = “leetcode”
输出：“tcode”

提示：

1 <= s.length <= 4 * 105
s 仅含有小写英文字符。

#思路：
滑动窗口

java代码：

class Solution {
public String lastSubstring(String s) {
        int length = s.length();
        if (length == 1) {
            return s;
        }
        char[] charArray = s.toCharArray();
        int startIndex = 0;
        int endIndex = 1;

        while (endIndex < length) { // 滑动窗口末端
            if (charArray[startIndex] < charArray[endIndex]) { // 1. 遇到比起始字符大的字符时，窗口整体跳到较大字符处
                startIndex = endIndex;
                endIndex++;
            } else if (charArray[startIndex] > charArray[endIndex]) { // 2.后续字符小于起始字符时，窗口末端右移
                endIndex++;
            } else { // 3.遇到相等的字符时，分别从两个下标开始对比两个子串
                int tempIndex = 1; // 临时增量
                while (endIndex + tempIndex < length) { // 子串滑动窗口末端
                    if (charArray[startIndex] < charArray[endIndex + tempIndex]) { // 子串出现较大字符
                        startIndex = endIndex + tempIndex;
                        endIndex = endIndex + tempIndex;
                        break;
                    }
                    if (charArray[startIndex + tempIndex] < charArray[endIndex + tempIndex]) { // 3.1第二子串较大,窗口起始点跳到第二子串起始处
                        startIndex = endIndex;
                        break;
                    }
                    if (charArray[startIndex + tempIndex] > charArray[endIndex + tempIndex]) { // 3.2第一子串较大，第一子串窗口末端扩到第二子串末端
                        endIndex = endIndex + tempIndex;
                        break;
                    }
                    if (charArray[startIndex + tempIndex] == charArray[endIndex + tempIndex]) { // 3.3俩当前子串相等，继续对比俩子串
                        tempIndex++;
                    }
                    if (endIndex + tempIndex >= length) { // 3.4第二子串窗口末端到顶部，说明未找到比第一子串大的字符，同3.2，结束对比
                        endIndex = endIndex + tempIndex;
                        break;
                    }
                }
                endIndex++;
            }
        }
        return s.substring(startIndex);
 }
}


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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48