[LeetCode] 1163. Last Substring in Lexicographical Order
grandyang opened this issue · 0 comments
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://leetcode.com/problems/last-substring-in-lexicographical-order/