1163. Last Substring in Lexicographical Order

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. 1 <= s.length <= 4 * 10^5
  2. s contains only lowercase English letters.

Rust Solution

struct Solution;
use std::cmp::Ordering::*;

impl Solution {
    fn last_substring(s: String) -> String {
        let n = s.len();
        let mut i = 0;
        let mut j = 1;
        let mut k = 0;
        let v = s.as_bytes();
        while j + k < n {
            match v[i + k].cmp(&v[j + k]) {
                Equal => {
                    k += 1;
                }
                Greater => {
                    j = j + k + 1;
                    k = 0;
                }
                Less => {
                    i = j.max(i + k + 1);
                    j = i + 1;
                    k = 0;
                }
            }
        }
        s[i..].to_string()
    }
}

#[test]
fn test() {
    let s = "abab".to_string();
    let res = "bab".to_string();
    assert_eq!(Solution::last_substring(s), res);
    let s = "leetcode".to_string();
    let res = "tcode".to_string();
    assert_eq!(Solution::last_substring(s), res);
}

Having problems with this solution? Click here to submit an issue on github.