跳到主要内容

1163.按字典序排在最后的子串

链接：1163.按字典序排在最后的子串
难度：Hard
标签：双指针、字符串
简介：给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

题解 1 - typescript​

  • 编辑时间：2023-04-24
  • 执行用时：2020ms
  • 内存消耗：51MB
  • 编程语言：typescript
  • 解法介绍：同上。
function lastSubstring(s: string): string {
    let max = s;
    for (let i = 1; i < s.length; i++) {
        const subs = s.substring(i);
        if (max < subs) max = subs;
    }
    return max;
};

题解 2 - cpp​

  • 编辑时间：2023-04-24
  • 执行用时：44ms
  • 内存消耗：25.8MB
  • 编程语言：cpp
  • 解法介绍：先找到最末尾的字符，再对该字符为起点到结尾的字符串进行比较。
class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size(), imax = 0;
        vector<int> idxs;
        for (int i = 0; i < n; i++) {
            if (s[imax] < s[i]) imax = i, idxs.clear();
            if (s[imax] == s[i]) idxs.push_back(i);
        }
        imax = 0;
        for (int i = 1; i < idxs.size(); i++) {
            int i1 = idxs[imax] + 1, i2 = idxs[i] + 1;
            while (i2 < n && s[i1] == s[i2]) i1++, i2++;
            if (i2 == n) break;
            if (s[i1] < s[i2]) imax = i;
        }
        return s.substr(idxs[imax], n - idxs[imax]);
    }
};

题解 3 - rust​

  • 编辑时间：2023-04-24
  • 执行用时：16ms
  • 内存消耗：5.9MB
  • 编程语言：rust
  • 解法介绍：同上。
fn str_to_vec(s: &String) -> Vec<char> {
    s.chars().collect()
}
impl Solution {
    pub fn last_substring(s: String) -> String {
        let s = str_to_vec(&s);
        let n = s.len();
        let mut imax = 0;
        let mut idxs = vec![];
        for i in 0..n {
            if (s[imax] as u8) < (s[i] as u8) {
                imax = i;
                idxs.clear();
            }
            if (s[imax] as u8) == (s[i] as u8) {
                idxs.push(i);
            }
        }
        imax = 0;
        for i in 1..idxs.len() {
            let (mut i1, mut i2) = (idxs[imax] + 1, idxs[i] + 1);
            while i2 < n && s[i1] == s[i2] {
                i1 += 1;
                i2 += 1;
            }
            if i2 == n {
                break;
            }
            if s[i1] < s[i2] {
                imax = i;
            }
        }
        String::from_utf8(s[idxs[imax]..].iter().map(|v| *v as u8).collect()).unwrap()
    }
}

题解 4 - python​

  • 编辑时间：2023-04-24
  • 执行用时：6360ms
  • 内存消耗：18MB
  • 编程语言：python
  • 解法介绍：对所有末尾字符串做比较。
class Solution:
  def lastSubstring(self, s: str) -> str:
      return max(s[i:] for i in range(len(s)))