Last Substring in Lexicographical Order - Solution & Explanation
Problem Statement
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 * 105scontains only lowercase English letters.
Approach Overview
Problem Overview: Given a string s, return the substring that is lexicographically largest among all possible substrings. Every suffix of the string is a candidate, so the task reduces to finding the maximum suffix in dictionary order.
Approach 1: Suffix Comparison Using Two Pointers (O(n) time, O(1) space)
This optimal approach treats the problem as finding the best starting index of a suffix. Maintain two candidate indices i and j with an offset k. Compare characters s[i + k] and s[j + k]. If they match, increase k. If one suffix is smaller, discard it by moving the pointer forward past the compared range. The key insight: once a suffix loses a comparison, every prefix of that suffix also loses, so you can skip a whole block of candidates instead of checking each one. This creates a linear scan over the string without revisiting characters. The final index points to the lexicographically largest suffix, which is the required substring. This technique resembles competitive suffix comparison strategies and works well for problems involving two pointers and heavy string comparisons.
Approach 2: Suffix Array with LCP (O(n log n) time, O(n) space)
Another method constructs a suffix array containing all suffix starting positions sorted lexicographically. Once built, the answer is simply the last suffix in the sorted order because suffix arrays store suffixes in dictionary order. Building the array typically involves sorting based on ranks of prefix pairs and doubling the comparison length each round. An optional LCP (Longest Common Prefix) array helps optimize comparisons when sorting suffixes. Although asymptotically slower than the two-pointer technique, suffix arrays provide a general-purpose structure for many advanced string problems such as substring queries, pattern matching, and lexicographic ranking. Use this approach when practicing deeper string algorithms or when a reusable suffix index is needed.
Recommended for interviews: The two-pointer linear scan is the expected solution. It achieves O(n) time and constant memory while demonstrating strong reasoning about suffix comparisons. Building a suffix array proves you understand advanced string processing but is heavier than necessary for this specific problem.
Approach 1: Approach 1: Suffix Comparison Using Two Pointers
This approach uses two pointers to compare suffixes starting at different indices. Essentially, iterate over the possible starting positions using a greedy method to determine which leads to the lexicographically largest suffix.
The code uses three pointers: i to mark the current best candidate for the start of the lexicographical maximum suffix, j for the current suffix start position being compared, and k for the matching process length. The loop continues until the comparison reaches the end of the string, and updates the pointers accordingly to track the maximal suffix.
Code
Python
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the string since each pointer advances linearly through the string.
Space Complexity: O(1) as we are using a constant amount of extra space.
Approach 2: Approach 2: Suffix Array with LCP
Another approach to solving the problem involves constructing a suffix array and using the longest common prefix (LCP) array to determine the lexicographical order.
This C++ solution constructs a suffix array by iterating through all suffixes of the string. The array is sorted according to the lexicographical order of the suffixes. The suffix that appears last in the lexicographical order is then obtained directly from the sorted suffix array.
Complexity
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(n), required to store the suffix array and intermediate substrings.
Approach 3: 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.
We use two pointers i and j, where pointer i points to the starting position of the current largest substring with the largest dictionary order, and pointer j points to the starting position of the current substring being considered. In addition, we use a variable k to record the current position being compared. Initially, i = 0, j=1, k=0.
Each time, we compare s[i+k] and s[j+k]:
If s[i + k] = s[j + k], it means that s[i,..i+k] and s[j,..j+k] are the same, and we add k by 1 and continue to compare s[i+k] and s[j+k];
If s[i + k] \lt s[j + k], it means that the dictionary order of s[j,..j+k] is larger. At this time, we update i = i + k + 1, and reset k to 0. If i geq j at this time, we update pointer j to i + 1, that is, j = i + 1. Here we skip all suffix substrings with s[i,..,i+k] as the starting position, because their dictionary orders are smaller than the suffix substrings with s[j,..,j+k] as the starting position.
Similarly, if s[i + k] \gt s[j + k], it means that the dictionary order of s[i,..,i+k] is larger. At this time, we update j = j + k + 1 and reset k to 0. Here we skip all suffix substrings with s[j,..,j+k] as the starting position, because their dictionary orders are smaller than the suffix substrings with s[i,..,i+k] as the starting position.
Finally, we return the suffix substring starting from i, that is, s[i,..,n-1].
The time complexity is O(n), where n is the length of string s. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Suffix Comparison Using Two Pointers | Time Complexity: O(n), where n is the length of the string since each pointer advances linearly through the string. |
| Approach 2: Suffix Array with LCP | Time Complexity: O(n log n), due to the sorting step. |
| Two pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Suffix Comparison Using Two Pointers | O(n) | O(1) | Best general solution. Interview‑preferred for large strings and optimal performance. |
| Suffix Array with LCP | O(n log n) | O(n) | Useful when learning suffix arrays or when the sorted suffix structure is needed for other string queries. |
Video Solution
LeetCode 1163. Last Substring in Lexicographical Order • Happy Coding • 5,907 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Last Substring in Lexicographical Order easy or hard?
Last Substring in Lexicographical Order Python/Java solution
How to solve Last Substring in Lexicographical Order in O(n)?
What is the best approach for Last Substring in Lexicographical Order?
Is Last Substring in Lexicographical Order asked at Google/Amazon/Meta?
What data structure is used in Last Substring in Lexicographical Order?
What is the time complexity of Last Substring in Lexicographical Order?
Ready to solve this problem?
Practice Last Substring in Lexicographical Order with our built-in code editor and test cases.
Practice on FleetCode