class Solution {
public:
string lastSubstring(string s) {
}
};
1163. 按字典序排在最后的子串
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入：s = "abab" 输出："bab" 解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：
输入：s = "leetcode" 输出："tcode"
提示：
1 <= s.length <= 4 * 105s 仅含有小写英文字符。原站题解
python3 解法, 执行用时: 6188 ms, 内存消耗: 17.8 MB, 提交时间: 2023-04-24 10:02:05
class Solution:
def lastSubstring(self, s: str) -> str:
return max(s[i:] for i in range(len(s)))
golang 解法, 执行用时: 16 ms, 内存消耗: 7.1 MB, 提交时间: 2023-04-24 10:01:53
func max(a, b int) int {
if a > b {
return a
}
return b
}
func lastSubstring(s string) string {
i, j, n := 0, 1, len(s)
for j < n {
k := 0
for j + k < n && s[i + k] == s[j + k] {
k++
}
if j + k < n && s[i + k] < s[j + k] {
i, j = j, max(j + 1, i + k + 1)
} else {
j = j + k + 1
}
}
return s[i:]
}
java 解法, 执行用时: 15 ms, 内存消耗: 44.3 MB, 提交时间: 2023-04-24 10:01:29
class Solution {
public String lastSubstring(String s) {
int i = 0, j = 1, n = s.length();
while (j < n) {
int k = 0;
while (j + k < n && s.charAt(i + k) == s.charAt(j + k)) {
k++;
}
if (j + k < n && s.charAt(i + k) < s.charAt(j + k)) {
int t = i;
i = j;
j = Math.max(j + 1, t + k + 1);
} else {
j = j + k + 1;
}
}
return s.substring(i);
}
}
javascript 解法, 执行用时: 72 ms, 内存消耗: 46.3 MB, 提交时间: 2023-04-24 10:01:08
/**
* @param {string} s
* @return {string}
*/
var lastSubstring = function(s) {
let i = 0, j = 1, n = s.length;
while (j < n) {
let k = 0;
while (j + k < n && s[i + k] === s[j + k]) {
k++;
}
if (j + k < n && s[i + k] < s[j + k]) {
let t = i;
i = j;
j = Math.max(j + 1, t + k + 1);
} else {
j = j + k + 1;
}
}
return s.substring(i, n);
};
python3 解法, 执行用时: 328 ms, 内存消耗: 17.7 MB, 提交时间: 2023-04-24 09:57:33
class Solution:
def lastSubstring(self, s: str) -> str:
i, j, n = 0, 1, len(s)
while j < n:
k = 0
while j + k < n and s[i + k] == s[j + k]:
k += 1
if j + k < n and s[i + k] < s[j + k]:
i, j = j, max(j + 1, i + k + 1)
else:
j = j + k + 1
return s[i:]