1163. Last Substring in Lexicographical Order

Given a string s, return  the last substring of  s  in lexicographical order.

Example 1:

Input: s = "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: s = "leetcode"
Output: "tcode"

Constraints:

  • 1 <= s.length <= 4 * 105
  • s contains only lowercase English letters.

这道题给了一个字符串s,让返回其字母顺序最大的一个子串。所谓字母顺序就是字典顺序,按字母表的顺序进行排列,比如 ba 大于 abc,bca 大于 bc,等等。那么为了让字母顺序最大,子串的第一个字母肯定是越大越好,所以若s中不存在重复字母的话,那么只要找最大字母开头的子串就行了,比如 abedc,就知道是 edc 了。但是若存在重复字母,比如 abeced,可以发现 eced 是小于 ed 的,所以就没法直接找到。但是当两个e的位置确定了,就可以一个个的接着往下比较,当后的字母相同时,接续比较下一对,若不同时,则要进行更新,这就是经典的双指针的操作,这里用两个指针i和j,i指向s的第一个字母,j指向第二个字母,用个变量 len 表示当前已经比较的个数。进行循环,条件是 j+len 小于n,若 s[i+len] 等于 s[j+len],说明对应的字母相等,增加 len 的长度。若 s[i+len] 小于 s[j+len],说明前面的子串的字母顺序小,此时i更新为 max(i + len + 1, j),并重置 len 为0。想一想为啥要这么更新呢,当s是 aaaaaab,i=0,j=1 时,可以发现 len 一直可以增加到5,然后出现不同,此时 i+len+1 是要大于j的,可以避免重复比较。而当s是 edcbaf,i=0,j=5,len=0 时,此时j是大于 i+len+1 的,可以避免重复比较。再来看最后一种情况, 若 s[i+len] 大于 s[j+len],说明此时i开头的子串大,由于j后面的 len 个字母都比较过了,所以此时j加上 len+1,并重置 len 为0。最终返回以i位置开头的子串即为所求,参见代码如下:

class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size(), i = 0, j = 1, len = 0;
        while (j + len < n) {
            if (s[i + len] == s[j + len]) ++len;
            else if (s[i + len] < s[j + len]) {
                i = max(i + len + 1, j);
                j = i + 1;
                len = 0;
            } else {
                j += len + 1;
                len = 0;
            }
        }
        return s.substr(i);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1163

参考资料:

https://leetcode.com/problems/last-substring-in-lexicographical-order/

https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/582703/C%2B%2B-SIMPLE-EASY-SOLUTION-WITH-EXPLANATION-CHEERS!!!

https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/363662/Short-python-code-O(n)-time-and-O(1)-space-with-proof-and-visualization

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation