题目描述

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

示例 1：

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

示例 2：

输入："leetcode"
输出："tcode"

题目分析

1. 题目结果一定是最大字母到结尾的字符串。
2. 使用双指针进行遍历，对比双指针向右偏移x的字母，直到 s[i+x] != s[j+x]。
3. 若s[i+x] < s[j+x]则将i指向j的位置，直至到最后一个字符，s.substring(i)即为所求答案。

C++代码

    string lastSubstring(string s) {
        int st = 0;
        int len = s.size();
        for(int i = 1; i < len; i++) {
            int sz = 0;
            while(i+sz < len && s[st + sz] == s[i + sz]) {
                sz++;
            }
            if(s[i + sz] > s[st + sz]) st = i;
            if(i+sz == len) break;
        }
        return s.substr(st);
    }