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 <= s.length <= 10^5
- s contains only lowercase English letters.
Key observation: The last substring must be a suffix of the original string, can’t a substring in the middle since we can always extend it.
e.g. leetcode -> tcode, can’t be “t”, “tc”, “tco”, “tcod”
Solution 1: Brute Force
Try all possible suffixes.
Time complexity: O(n^2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua, 452 ms, 12.8 MB class Solution { public: string lastSubstring(string_view s) { string_view ans; for (int i = 0; i < s.length(); ++i) if (s.substr(i) > ans) ans = s.substr(i); return string(ans); } }; |
Solution 2: Keep max and compare with candidates
Find the first largest letter as a starting point, whenever there is a same letter, keep it as a candidate and compare with the current best. If the later is larger, take over the current best.
e.g. “acbacbc”
“c” > “a”, the first “c” becomes the best.
“c” = “c”, the second “c” becomes a candidate
starting compare best and candidate.
“cb” = “cb”
“cba” < “cbc”, cand_i is the new best.
Time complexity: O(n)
Space complexity: O(1)
C++
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 |
// Author: Huahua class Solution { public: string lastSubstring(string s) { int max_i = 0; char max_c = 0; int cand_i = 0; int l = 0; for (int i = 0; i < s.length(); ++i) { if (s[i] > max_c) { // Find a better starting point. max_c = s[i]; max_i = i; cand_i = -1; l = 1; } else if (cand_i != -1) { // Has a candidate. if (s[i] > s[max_i + l]) { // The candidate is larger. max_i = cand_i; cand_i = -1; } else if (s[i] == s[max_i + l]) { // The candidate is the same as current best. ++l; } else { // The candidate is smaller, no longer needed. cand_i = -1; } } else if (s[i] == max_c) { // Find a new candidate, starting with length 1. cand_i = i; l = 1; } } return s.substr(max_i); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment