Last Substring in Lexicographical Order
HardPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
The problem asks for the lexicographically largest substring. A key observation is that the largest substring must be a suffix of the original string. If we have a maximal substring s[i...j], the suffix s[i...n-1] is always lexicographically greater than or equal to s[i...j] because s[i...j] is a prefix of s[i...n-1]. Therefore, we only need to find the lexicographically largest suffix of the string s.
Algorithm
- Get the length of the string,
n. - Initialize a variable
maxSubstringto an empty string or the first suffix. - Iterate with a pointer
ifrom0ton-1. - In each iteration, create the suffix starting at
i(s.substring(i)). - Compare this
currentSuffixwithmaxSubstringusingcompareTo. - If
currentSuffixis lexicographically larger, updatemaxSubstring = currentSuffix. - After the loop finishes, return
maxSubstring.
Walkthrough
This approach iterates through all possible suffixes of the string s. We maintain a variable, for instance maxSubstring, that stores the lexicographically largest suffix found so far. We can initialize maxSubstring with an empty string. Then, we loop with an index i from 0 to n-1, considering the suffix starting at i in each iteration. We compare the current suffix with maxSubstring. If the current suffix is lexicographically greater, we update maxSubstring. After checking all suffixes, the final value of maxSubstring is the answer. To be slightly more optimal, we can store the index of the maximal suffix instead of the string itself to reduce space usage during the loop, but the time complexity remains the same.
public String lastSubstring(String s) { int n = s.length(); String maxSubstring = ""; for (int i = 0; i < n; i++) { String currentSuffix = s.substring(i); if (currentSuffix.compareTo(maxSubstring) > 0) { maxSubstring = currentSuffix; } } return maxSubstring;}Complexity
Time
O(n^2) - The main loop runs `n` times. Inside the loop, creating a substring `s.substring(i)` can take O(n) time, and comparing it with another string of length up to O(n) also takes O(n) time. This results in a total time complexity of O(n * n) = O(n^2).
Space
O(n) - In each iteration, `s.substring()` can create a new string object of length up to O(n). The `maxSubstring` also stores a string of up to length O(n).
Trade-offs
Pros
Simple to understand and straightforward to implement.
Cons
Highly inefficient due to repeated substring creation and comparison.
The time complexity of O(n^2) will cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution {public String lastSubstring(String s) { int n = s.length(); int i = 0; for (int j = 1, k = 0; j + k < n;) { int d = s.charAt(i + k) - s.charAt(j + k); if (d == 0) { ++k; } else if (d < 0) { i += k + 1; k = 0; if (i >= j) { j = i + 1; } } else { j += k + 1; k = 0; } } return s.substring(i); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.