Last Substring in Lexicographical Order solution and explanation
IBM
9 more videos on this problem
LeetCode 1163. Last Substring in Lexicographical OrderHappy Coding · 23:56 · 5K views
LeetCode 1163. Last Substring in Lexicographical OrdercoderZ · 8:02 · 3K views
Last Substring in Lexicographical Order || LeetCodeSiddharth Nagaych · 7:10 · 952 views
1163. Last Substring in Lexicographical Order - LeetCode - [ Must do for Problem 3403 ]Intuit & Code · 35:50 · 733 views
Finding the last substring in lexicographical order in O(n) time (2 Solutions!!)Roel Van de Paar · 1:53 · 531 views
Leetcode 1163. Last Substring in Lexicographical Order (two pointers)LetsCode · 11:12 · 447 views
1163. Last Substring in Lexicographical OrderJust Coding, with Jie · 28:23 · 175 views
No Sound Leetcode 1163: Last Substring in Lexicographical OrderExtremeProgrammer · 0:52 · 59 views
LeetCode 1163: Last Substring in Lexicographical OrderAlitaCode · 28:08 · 26 views
LeetCode Problem #1163 Last Substring in Lexicographical order神戸万事屋 · 0:52
The 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 * 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.
def lastSubstring(s: str) -> str:
i, j, k = 0, 1, 0
n = len(s)
while j + k < n:
if s[i + k] == s[j + k]:
k += 1
elif s[i + k] < s[j + k]:
i = max(i + k + 1, j)
j = i + 1
k = 0
else:
j = j + k + 1
k = 0
return s[i:]function lastSubstring(s) {
let i = 0, j = 1, k = 0, n = s.length;
while (j + k < n) {
if (s[i + k] === s[j + k]) {
k++;
} else if (s[i + k] < s[j + k]) {
i = Math.max(i + k + 1, j);
j = i + 1;
k = 0;
} else {
j = j + k + 1;
k = 0;
}
}
return s.substring(i);
}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.
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.
import java.util.Comparator;
import java.util.Arrays;
public class Solution {
public String lastSubstring(String s) {
int n = s.length();
Integer[] suffixArray = new Integer[n];
for (int i = 0; i < n; i++) suffixArray[i] = i;
Arrays.sort(suffixArray, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return s.substring(a).compareTo(s.substring(b));
}
});
return s.substring(suffixArray[n - 1]);
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string lastSubstring(string s) {
int n = s.size();
vector<int> suffixArray(n);
for (int i = 0; i < n; ++i) suffixArray[i] = i;
sort(suffixArray.begin(), suffixArray.end(), [&s](int a, int b) {
return s.substr(a) < s.substr(b);
});
return s.substr(suffixArray.back());
}In the Java implementation, we form an integer array representing suffix indices, sort it lexicographically by comparing suffixes directly using substring operations. The resulting suffix at the final position is the desired substring.
Time Complexity: O(n log n), primarily due to sorting.
Space Complexity: O(n), primarily to store suffix indices.
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).
function lastSubstring(s: string): string {
const n = s.length;
let i = 0;
for (let 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.slice(i);
}func lastSubstring(s string) string {
i, n := 0, len(s)
for j, k := 1, 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[i:]
}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), primarily due to sorting. |
| Two pointers | – |
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. |
Frequently asked questions
Is Last Substring in Lexicographical Order easy or hard?
LeetCode classifies this problem as Hard because the optimal O(n) solution relies on a non-obvious suffix elimination strategy. Many first attempts use brute force suffix generation or sorting, which leads to O(n^2) or O(n log n) complexity.
Last Substring in Lexicographical Order Python/Java solution
Python and JavaScript implementations usually apply the O(n) two-pointer suffix comparison method because it requires only index arithmetic and character comparisons. C++ and Java implementations sometimes demonstrate suffix array construction for educational purposes.
How to solve Last Substring in Lexicographical Order in O(n)?
Maintain two candidate suffix indices i and j along with an offset k. Compare characters s[i+k] and s[j+k]. When characters differ, discard the smaller suffix by moving its pointer forward past the compared segment and reset k. Continue until one candidate reaches the end; the remaining index marks the largest suffix.
What is the best approach for Last Substring in Lexicographical Order?
The most efficient approach uses a two-pointer suffix comparison technique. Two candidate starting indices are compared while skipping dominated suffixes, ensuring each character is processed at most a few times. This yields O(n) time and O(1) space, making it the optimal solution for large strings.
Is Last Substring in Lexicographical Order asked at Google/Amazon/Meta?
Variants of suffix comparison and lexicographically maximum substring problems appear in interviews at large tech companies including Google and Amazon. These companies often test understanding of linear-time string algorithms, suffix structures, and pointer-based comparisons.
What data structure is used in Last Substring in Lexicographical Order?
The optimal solution relies mainly on pointer indices and character comparisons rather than complex data structures. An alternative solution uses a suffix array along with an optional LCP array, which are classic structures in advanced string processing.
What is the time complexity of Last Substring in Lexicographical Order?
The optimal two-pointer algorithm runs in O(n) time with O(1) additional space. A suffix array based solution typically takes O(n log n) time and O(n) space due to sorting suffix ranks. Both methods produce the same result but the linear scan is faster.