题目描述

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. 1 <= s.length <= 4 * 10^5
2. s contains only lowercase English letters.

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

算法1

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

题解：首先我们知道，答案肯定是字符串s的后缀，否则我们将后续字符串拼接在答案的后面可以得到一个字典序更高的字符串。其次，我们知道答案的首字符肯定是出现过的ASCII码最大的字符，那么记录这些位置我们得到一个答案起始位置候选集合，接下来我们根据这个集合去查看下一位次的字符，不断的缩小这个集合，直到集合大小为1。

这里有个十分重要的优化点在于，在初始化的时候如果有多个连续字符相邻，我们只需要取首尾两个位置加入候选集合就可以了，中间的字符绝对不可能是答案。比如：

s = "bbba" 紧跟在后面的字符a小于重复字符b的情况：
这时候字典序最大的是重复字符串首位置作为起始位置 "bbba"

s = "bbbc" 紧跟在后面的字符c大于重复字符b的情况
这时候字典许最大的是重复字符串末尾位置作为起始位置 “bc”

    string lastSubstring(string s) {
        vector<int> candidate_start;
        vector<int> tmp;
        int n = s.length(),cur_length = 0;
        for(int i = 0 ; i < s.length(); i ++){
            if(i > 0 && i < n - 1 && s[i] == s[i - 1] && s[i] == s[i + 1]) continue;
            candidate_start.push_back(i);
        }
        while(candidate_start.size() > 1){
            char max_char = 'a';
            for(auto idx : candidate_start){
                if(idx + cur_length >= n){
                    break;
                }
                if(s[idx + cur_length] > max_char){
                    tmp.resize(0);
                    tmp.push_back(idx);
                    max_char = s[idx + cur_length];
                }else if(s[idx + cur_length] == max_char){
                    tmp.push_back(idx);
                }
            }
            candidate_start.assign(tmp.begin(),tmp.end());
            tmp.resize(0);
            cur_length ++;
        }
        return s.substr(candidate_start[0],n - candidate_start[0]);
    }