Watch 8 video solutions for Last Substring in Lexicographical Order, a hard level problem involving Two Pointers, String. This walkthrough by Happy Coding has 5,793 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 105s contains only lowercase English letters.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 | 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. |