Problem Description

Given a string s, you are asked to find the last substring in lexicographical order among all possible non-empty substrings of s. You must return this substring as a string.

• You are guaranteed that there is exactly one valid solution.
• The substring must be a contiguous part of s.
• All characters in s are lowercase English letters.
• You cannot reuse characters from different positions; the substring must be a slice of the original string.

Example:
Input: s = "abab"
Output: "bab"

Thought Process

At first glance, the brute-force approach would be to generate all possible substrings of s and compare them to find the largest in lexicographical order. However, this is highly inefficient, especially for long strings, since the number of substrings is quadratic in the length of s.

To optimize, we should recognize that the "last" substring in lexicographical order must start at one of the positions where the largest character occurs. For example, if 'z' is the largest character, the answer must start at a position where 'z' appears.

We can further optimize by comparing suffixes starting at each candidate position, but we want to avoid comparing the same substrings repeatedly. The problem is similar to finding the maximal suffix or using the "two pointers" technique to compare possible starting positions efficiently.

Solution Approach

• Step 1: Identify the largest character.
  Since the last substring must start with the largest character, find all positions where this character occurs.
• Step 2: Use Two Pointers to Compare Suffixes.
  Use two pointers, i and j, to represent candidate starting positions. Always keep i as the current best and j as the next candidate.
• Step 3: Compare the substrings starting at i and j.
  For each offset k, compare s[i + k] and s[j + k]:
  • If they are equal, increment k.
  • If s[i + k] > s[j + k], j cannot be the answer, so move j forward.
  • If s[i + k] < s[j + k], i cannot be the answer, so move i forward (to j), and move j to i + 1.
• Step 4: Continue until j reaches the end.
  The substring starting at i will be the answer.

This approach is efficient because it avoids redundant substring comparisons and only compares as much as necessary to decide which starting index is better.

Example Walkthrough

Example Input: s = "abab"

1. The largest character is 'b', which appears at indices 1 and 3.
2. Compare substrings starting at 1 ("bab") and at 3 ("b"):
3. - Compare 'b' vs 'b': equal, move to next character.
   - Compare 'a' vs '' (end of string): since the right substring is exhausted, "bab" is larger.
4. The answer is the substring starting at index 1: "bab".

The process efficiently eliminates other candidates by direct comparison, never generating all substrings.

Time and Space Complexity

• Brute-force approach:
  Generating all substrings would take O(n²) time and O(n²) space, where n is the length of s.
• Optimized approach:
  The two-pointer comparison ensures that each character is compared at most twice, leading to O(n) time and O(1) extra space.

This efficiency comes from never revisiting the same substring comparison and always moving at least one pointer forward.

Summary

The key insight is that the last lexicographical substring must start at one of the positions with the largest character. By using a two-pointer technique, we efficiently compare candidate substrings without generating all possibilities. This leads to an elegant, linear-time solution that leverages properties of lexicographical order and suffix comparison.

Code Implementation

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

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

class Solution {
    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++;
            } else if (s.charAt(i + k) > s.charAt(j + k)) {
                j = j + k + 1;
                k = 0;
            } else {
                i = Math.max(i + k + 1, j);
                j = i + 1;
                k = 0;
            }
        }
        return s.substring(i);
    }
}
      

var lastSubstring = function(s) {
    let n = s.length;
    let i = 0, j = 1, k = 0;
    while (j + k < n) {
        if (s[i + k] === s[j + k]) {
            k++;
        } else if (s[i + k] > s[j + k]) {
            j = j + k + 1;
            k = 0;
        } else {
            i = Math.max(i + k + 1, j);
            j = i + 1;
            k = 0;
        }
    }
    return s.substring(i);
};