1163. Last Substring in Lexicographical Order

Description

Given a string s, return the last substring of s in lexicographical order.

 

Example 1:

Input: s = "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: s = "leetcode"
Output: "tcode"

 

Constraints:

• 1 <= s.length <= 4 * 105
• s contains only lowercase English letters.

 

Solutions

Solution: Two Pointers

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
const lastSubstring = function (s) {
  const n = s.length;
  let a = 0;
  let b = 1;
  let length = 1;

  while (b + length <= n) {
    const letterA = s[a + length - 1];
    const letterB = s[b + length - 1];

    if (letterA === letterB) length += 1;
    else if (letterA < letterB) {
      a = Math.max(a + length, b);
      b = a + 1;
      length = 1;
    } else {
      b += length;
      length = 1;
    }
  }
  return s.slice(a);
};