Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1163.html
1163. Last Substring in Lexicographical Order (Hard)
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.
Companies:
Mathworks
Related Topics:
String
Solution 1. Brute Force
First, find the greatest character, with which the answer must start.
Push all the indexes of that character into a candidate vector, which are all the possible solutions.
Note that considering the case "a............a"
, we only push if the character before the current index is not also the greatest character. This is because in that case, the previous index must yield better result than the current index (For example, for "ddab"
and "dab"
, we don’t need to consider "dab"
).
Now we have all the possible start indexes, we continue to look at the 2nd, 3rd, … characters after the start indexes.
- If this start index can’t afford
len
characters after it but others can, it should be ignored. - For each start indexes
n
, we look at thes[n + len]
, and find the greatest character. We only keep the start indexes that has the greatest character we just found ats[n + len]
.
As we extending the len
, the size of the available start indexes gets smaller and smaller until it becomes 1. The last start index left is the start index of the answer.
// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(VL) where V is the length of `v` and L is the max possible `len`.
// It is strictly smaller than O(N^2)
// Space: O(N)
class Solution {
public:
string lastSubstring(string s) {
int start = 0, N = s.size();
for (int i = 0; i < N; ++i) {
if (s[i] > s[start]) start = i;
}
vector<int> v;
for (int i = start; i < N; ++i) {
if (s[i] == s[start] && (i == 0 || s[i - 1] != s[start])) v.push_back(i);
}
for (int len = 1; len <= N && v.size() > 1; ++len) {
vector<int> next;
char c = 'a';
for (int n : v) {
if (n + len >= N || s[n + len] < c) continue;
if (s[n + len] > c) {
next.clear();
c = s[n + len];
}
next.push_back(n);
}
v = next;
}
return s.substr(v[0]);
}
};
Solution 2. Brute Force
For a substring A
and all its prefix substrings, A
must be the one lexicographically largest. So we don’t need to consider the prefix substrings of A
.
So for this question, we only need to consider the N
suffix substrings of s
.
We just brute-forcely compare all the suffix strings.
One optimization we do for the "a.....a"
case is if (i + j == N) break
. My reasoning is as follows.
When i + j == N
, the string i
is of pattern ABA
, where j
is the start index of the second string segment A
.
Example
i j
[ddac](abac)[ddac]
Note that string A
and B
won’t have any character greater than s[i]
because otherwise i
will be moved to that greater character first.
Since we’ve already moved to s[j]
, it means there is no better solution between i+1
and j - 1
. So we only need to think about the indexes after j
. For each k
in [j + 1, N)
, we can find a counterpart t
in [i + 1, i + N - j)
, and string t
must be better than string k
since they have the same prefix and string t
is longer. And because string t
is no better than string i
, so we can ignore all indexes after j
.
Note that this optimization can’t pass test case "a....ab"
though.
// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(N^2)
// Space: O(1)
// Ref: https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/360957/C%2B%2B-Brute-Force
class Solution {
public:
string lastSubstring(string s) {
int start = 0, N = s.size(), j;
for (int i = 1; i < N; ++i) {
for (j = 0; i + j < N; ++j) {
if (s[start + j] == s[i + j]) continue;
start = s[start + j] > s[i + j] ? start : i;
break;
}
if (i + j == N) break;
}
return s.substr(start);
}
};
Solution 3. Brute Force
Same idea as Solution 2 but with different optimization.
We skip the start index i
if both s[i]
and s[i - 1]
are the same as s[start]
where start
is the best start index currently found.
It’s because in that case string i - 1
must be lexicographically larger than string i
.
This solution can pass the test case "a....ab"
.
// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
string lastSubstring(string s) {
int start = 0, N = s.size();
for (int i = 1; i < N; ++i) {
if (s[i] == s[start] && s[i - 1] == s[start]) continue;
for (int j = 0; i + j < N; ++j) {
if (s[start + j] == s[i + j]) continue;
start = s[start + j] > s[i + j] ? start : i;
break;
}
}
return s.substr(start);
}
};
-
class Solution { public String lastSubstring(String s) { char maxChar = 'a'; int length = s.length(); int index = length - 1; for (int i = length - 1; i >= 0; i--) { char c = s.charAt(i); if (c > maxChar) { index = i; maxChar = c; } else if (c == maxChar) { if (i > 0 && c == s.charAt(i - 1)) continue; int temp = index; index = i; for (int j = i, k = temp; j < length && k < length; j++, k++) { if (s.charAt(j) < s.charAt(k)) { index = temp; break; } else if (s.charAt(j) > s.charAt(k)) break; } } } return s.substring(index); } }
-
// OJ: https://leetcode.com/problems/last-substring-in-lexicographical-order/ // Time: O(N^2) // Space: O(1) // Ref: https://leetcode.com/problems/last-substring-in-lexicographical-order/discuss/360957/C%2B%2B-Brute-Force class Solution { public: string lastSubstring(string s) { int start = 0, N = s.size(), j; for (int i = 1; i < N; ++i) { for (j = 0; i + j < N; ++j) { if (s[start + j] == s[i + j]) continue; start = s[start + j] > s[i + j] ? start : i; break; } if (i + j == N) break; } return s.substr(start); } };
-
# 1163. Last Substring in Lexicographical Order # https://leetcode.com/problems/last-substring-in-lexicographical-order/ class Solution: def lastSubstring(self, s: str) -> str: biggest = max(s) res = "" for i,c in enumerate(s): if c == biggest: res = max(res, s[i:]) return res
-
func lastSubstring(s string) string { i, n := 0, len(s) for j, k := 1, 0; j+k < n; { if s[i+k] == s[j+k] { k++ } else if s[i+k] < s[j+k] { i += k + 1 k = 0 if i >= j { j = i + 1 } } else { j += k + 1 k = 0 } } return s[i:] }
-
function lastSubstring(s: string): string { const n = s.length; let i = 0; for (let j = 1, k = 0; j + k < n; ) { if (s[i + k] === s[j + k]) { ++k; } else if (s[i + k] < s[j + k]) { i += k + 1; k = 0; if (i >= j) { j = i + 1; } } else { j += k + 1; k = 0; } } return s.slice(i); }