#1163

Hard

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Last Substring in Lexicographical Order

Identify the lexicographically last substring in a string using two-pointer scanning with invariant tracking efficiently.

two pointers string

Problem Statement

Given a string s consisting of only lowercase English letters, find and return the substring that is last in lexicographical order. The substring must be contiguous and can span any length from 1 to the length of s.

For example, given s = "abab", the substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The substring with the highest lexicographical order is "bab". Return this as the output.

Examples

Example 1

Input: s = "abab"

Output: "bab"

The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2

Input: s = "leetcode"

Output: "tcode"

Example details omitted.

Constraints

1 <= s.length <= 4 * 105
s contains only lowercase English letters.

Solution Approach

Initialize two pointers and candidate index

Start with two pointers, i and j, representing the current candidate substring and a scanning pointer. Initialize i = 0 and j = 1. The invariant is that s[i:] is currently the lexicographically largest substring seen.

Scan and compare characters

While j is less than the string length, compare s[i+k] and s[j+k] for increasing k. If s[i+k] < s[j+k], update i to j and reset k. If s[i+k] > s[j+k], increment j by k+1. This step ensures we skip substrings that cannot be maximal.

Return the maximal substring

After scanning the string, the pointer i indicates the start of the last substring in lexicographical order. Return s[i:] as the answer. This approach avoids generating all substrings and uses linear comparisons efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is compared at most twice during the scanning process. Space complexity is O(1) aside from the input string, as only pointers and counters are maintained.

What Interviewers Usually Probe

Candidate quickly identifies two-pointer approach.
Candidate maintains a clear invariant for substring comparison.
Candidate explains skipping non-optimal substrings efficiently.

Common Pitfalls or Variants

Common pitfalls

Trying to generate all substrings, leading to O(n^2) time complexity.
Not handling equal character comparisons correctly, missing the correct candidate.
Resetting pointers incorrectly when a better substring is found, breaking the invariant.

Follow-up variants

Return the last substring in lexicographical order for uppercase letters.
Find the last substring when s contains both letters and digits.
Compute the last substring allowing wrap-around comparisons in a circular string.

FAQ

What is the best approach for 'Last Substring in Lexicographical Order'?

Use two pointers with invariant tracking, comparing characters incrementally to maintain the current maximal substring.

Can we generate all substrings to solve this problem?

Generating all substrings is inefficient, resulting in O(n^2) time, and is unnecessary with the two-pointer scanning method.

How does the two-pointer invariant work in this problem?

It tracks the current candidate for the maximal substring and skips over any starting indices that cannot produce a larger substring.

What are common mistakes when implementing this solution?

Mistakes include mismanaging pointer updates, incorrectly comparing equal characters, or attempting brute-force substring generation.

Is this approach applicable to variations with digits or uppercase letters?

Yes, the two-pointer scanning with invariant tracking works for any lexicographical order, including uppercase letters or digits.

terminal

Solution

Solution 1: Two pointers

We notice that if a substring starts from position $i$, then the largest substring with the largest dictionary order must be $s[i,..n-1]$, which is the longest suffix starting from position $i$. Therefore, we only need to find the largest suffix substring.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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:]

Continue Practicing

#1147 longest chunked palindrome decomposition #1048 longest string chain #1023 camelcase matching