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

Last updated