# Last Substring in Lexicographical Order
**Difficulty:** HARD
[External](https://leetcode.com/problems/last-substring-in-lexicographical-order)
Canonical: https://scaleengineer.com/dsa/problems/last-substring-in-lexicographical-order
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks), [Fastenal](https://scaleengineer.com/companies/fastenal)
---
## 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 * 105`
* `s` contains only lowercase English letters.

# Approaches
## Brute Force Suffix Comparison
The problem asks for the lexicographically largest substring. A key observation is that the largest substring must be a suffix of the original string. If we have a maximal substring `s[i...j]`, the suffix `s[i...n-1]` is always lexicographically greater than or equal to `s[i...j]` because `s[i...j]` is a prefix of `s[i...n-1]`. Therefore, we only need to find the lexicographically largest suffix of the string `s`.
**Time:** O(n^2) - The main loop runs `n` times. Inside the loop, creating a substring `s.substring(i)` can take O(n) time, and comparing it with another string of length up to O(n) also takes O(n) time. This results in a total time complexity of O(n * n) = O(n^2). · **Space:** O(n) - In each iteration, `s.substring()` can create a new string object of length up to O(n). The `maxSubstring` also stores a string of up to length O(n).
**Pros:** Simple to understand and straightforward to implement.
**Cons:** Highly inefficient due to repeated substring creation and comparison.; The time complexity of O(n^2) will cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
This approach iterates through all possible suffixes of the string `s`. We maintain a variable, for instance `maxSubstring`, that stores the lexicographically largest suffix found so far. We can initialize `maxSubstring` with an empty string. Then, we loop with an index `i` from `0` to `n-1`, considering the suffix starting at `i` in each iteration. We compare the current suffix with `maxSubstring`. If the current suffix is lexicographically greater, we update `maxSubstring`. After checking all suffixes, the final value of `maxSubstring` is the answer. To be slightly more optimal, we can store the index of the maximal suffix instead of the string itself to reduce space usage during the loop, but the time complexity remains the same.

```java
public String lastSubstring(String s) {
    int n = s.length();
    String maxSubstring = "";
    for (int i = 0; i < n; i++) {
        String currentSuffix = s.substring(i);
        if (currentSuffix.compareTo(maxSubstring) > 0) {
            maxSubstring = currentSuffix;
        }
    }
    return maxSubstring;
}
```
### Algorithm
- Get the length of the string, `n`.
- Initialize a variable `maxSubstring` to an empty string or the first suffix.
- Iterate with a pointer `i` from `0` to `n-1`.
- In each iteration, create the suffix starting at `i` (`s.substring(i)`).
- Compare this `currentSuffix` with `maxSubstring` using `compareTo`.
- If `currentSuffix` is lexicographically larger, update `maxSubstring = currentSuffix`.
- After the loop finishes, return `maxSubstring`.

## Optimized Two-Pointer Approach
This approach significantly improves upon the brute-force method by avoiding the explicit creation and comparison of entire substrings in each step. It uses a two-pointer technique to compare candidate suffixes in-place. The core idea is to maintain two pointers, `i` and `j`, pointing to the start of the current best suffix and a challenger suffix, respectively. A third variable, `k`, is used to track the length of their common prefix. When a mismatch is found, we can intelligently advance `i` or `j` by more than one position, skipping over many suffixes that are guaranteed not to be the maximal one. This leads to a linear time solution.
**Time:** O(n) - Although there's a loop within a loop, the pointers `i` and `j` only move forward. The total number of character comparisons is bounded by a linear function of `n`. In each step, either `k` increases, or the sum `i+j` increases. The total advancement of `i`, `j`, and `k` is O(n), making the overall time complexity linear. · **Space:** O(1) auxiliary space. The algorithm only uses a few integer variables (`i`, `j`, `k`). The space for the final returned substring is O(n) but is not counted as auxiliary space.
**Pros:** Highly efficient with an optimal time complexity of O(n).; Uses constant auxiliary space (excluding the space for the output string).
**Cons:** The logic, especially the pointer updates, is more complex and less intuitive than the brute-force approach.; The proof of correctness is non-trivial.
### Explanation
We use three integer variables: `i`, `j`, and `k`. `i` is the starting index of the current best candidate for the last substring. `j` is the starting index of the challenger substring. `k` is the offset from `i` and `j`, representing the length of the common prefix we have checked so far.

We iterate while `j + k` is within the bounds of the string. By comparing `s.charAt(i + k)` and `s.charAt(j + k)`, we decide which candidate to eliminate.

If `s.charAt(i + k) > s.charAt(j + k)`, the challenger `s[j:]` is smaller. We can prove that all suffixes starting from `j` to `j+k` are also smaller than `s[i:]`, so we can safely jump the challenger pointer `j` to `j + k + 1`.

If `s.charAt(i + k) < s.charAt(j + k)`, the current best `s[i:]` is smaller. It gets eliminated, and `s[j:]` becomes the new best candidate. We update `i` to `j` and continue searching for a new challenger from `j+1`. All suffixes between the old `i` and `j` have already lost to `s[old_i:]` and are therefore also smaller than the new best `s[j:]`.

This process of elimination continues until `j` scans past the end of the string. The final value of `i` gives the starting index of the lexicographically last substring.

```java
public String lastSubstring(String s) {
    int n = s.length();
    int i = 0, j = 1, k = 0;
    while (j + k < n) {
        if (s.charAt(i + k) == s.charAt(j + k)) {
            k++;
            continue;
        }
        if (s.charAt(i + k) > s.charAt(j + k)) {
            // Suffix at j is smaller, so it and its subsequent k suffixes are eliminated.
            j = j + k + 1;
        } else {
            // Suffix at i is smaller, so it's eliminated. j becomes the new candidate.
            i = j;
            j = i + 1;
        }
        k = 0;
    }
    return s.substring(i);
}
```
### Algorithm
- Get the length of the string, `n`.
- Initialize three pointers: `i = 0` (index of the best suffix candidate), `j = 1` (index of the challenger suffix), and `k = 0` (length of the common prefix between suffixes at `i` and `j`).
- Loop while `j + k < n`.
- **Case 1: `s.charAt(i + k) == s.charAt(j + k)`**
  - The characters match, so extend the common prefix by incrementing `k`.
- **Case 2: `s.charAt(i + k) > s.charAt(j + k)`**
  - The challenger suffix `s[j:]` is smaller than the current best `s[i:]`. We can discard not only `s[j:]` but also all suffixes starting from `j+1` to `j+k`. So, we advance the challenger pointer `j` to `j + k + 1` and reset `k` to `0`.
- **Case 3: `s.charAt(i + k) < s.charAt(j + k)`**
  - The current best suffix `s[i:]` is smaller than the challenger `s[j:]`. `s[i:]` is eliminated. The new best candidate is `s[j:]`. We update `i = j`, advance the challenger to `j = i + 1`, and reset `k` to `0`.
- After the loop terminates, the starting index of the last substring is `i`. Return `s.substring(i)`.

# Solutions
### Java

```java
class Solution {
public
  String lastSubstring(String s) {
    int n = s.length();
    int i = 0;
    for (int j = 1, k = 0; j + k < n;) {
      int d = s.charAt(i + k) - s.charAt(j + k);
      if (d == 0) {
        ++k;
      } else if (d < 0) {
        i += k + 1;
        k = 0;
        if (i >= j) {
          j = i + 1;
        }
      } else {
        j += k + 1;
        k = 0;
      }
    }
    return s.substring(i);
  }
}

```

### Python

```python
class Solution:
    def lastSubstring(self, s: str) -> str: i, j, k = 0, 1, 0 while j + k < len(s): if s[i + k] == s[j + k]: k += 1 elif s[i + k] < s[j + k]: i += k + 1 k = 0 if i >= j: j = i + 1 else: j += k + 1 k = 0 return s[i:]

```

### CPP

```cpp
class Solution { public: string lastSubstring ( string s ) { int n = s . size (); int i = 0 ; for ( int j = 1 , k = 0 ; j + k < n ;) { if ( s [ i + k ] == s [ j + k ]) { ++ k ; } else if ( s [ i + k ] < s [ j + k ]) { i += k + 1 ; k = 0 ; if ( i >= j ) { j = i + 1 ; } } else { j += k + 1 ; k = 0 ; } } return s . substr ( i ); } };
```