1163. Last Substring in Lexicographical Order

Problem

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 * 10^5

• s contains only lowercase English letters.

Solution

class Solution {
  public String lastSubstring(String s) {
    int n = s.length();
    int i = 0, j = 1, offset = 0;
    while (i < n && j < n) {
      if (i + offset >= n || j + offset >= n)        break;

      if (s.charAt(i + offset) == s.charAt(j + offset)) {
        offset++;
      } else {
        if (s.charAt(i + offset) < s.charAt(j + offset)) {
          i = Math.max(i + offset + 1, j + 1); 
        } else {
          j = Math.max(j + offset + 1, i + 1);
        }

          offset = 0;
      }
    }

    int l = Math.min(i, j);
    return s.substring(l);
  }
}

Explain:

nope.

Complexity:

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