1163.Last-Substring-in-Lexicographical-Order

1163. Last Substring in Lexicographical Order

题目地址

https://leetcode.com/problems/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 <= s.length <= 4 * 10^5
s contains only lowercase English letters.

代码

Approach #1 Two Pointers + offset

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);
  }
}

Approach #2

public String lastSubstring(String s) {
    int i = 0, j = 1, offset = 0, len = s.length();
    while (i + offset < len && j + offset < len) {
        char c = s.charAt(i + offset), d = s.charAt(j + offset);
        if (c == d) {
            ++offset;
        } else {
          // chars in [i, ..., i + offset] <= charAt(i) == charAt(j)
            if (c < d)  { 
              i = i + offset + 1; 
            } 
          // c > d, chars in [j, ..., j + offset] <= charAt(i) == charAt(j)
            else { 
              j = j + offset + 1; 
            } 

              // avoid duplicate start indices. 
              if (i == j) { 
              ++i; 
            } 

            offset = 0; // reset offset to 0.
        }
    }
    return s.substring(Math.min(i, j));
}