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.
This approach significantly improves upon the brute-force method by avoiding the explicit creation and comparison of entire substrings in each step. It uses a two-pointer technique to compare candidate suffixes in-place. The core idea is to maintain two pointers, i and j, pointing to the start of the current best suffix and a challenger suffix, respectively. A third variable, k, is used to track the length of their common prefix. When a mismatch is found, we can intelligently advance i or j by more than one position, skipping over many suffixes that are guaranteed not to be the maximal one. This leads to a linear time solution.
Algorithm
- Get the length of the string,
n. - Initialize three pointers:
i = 0(index of the best suffix candidate),j = 1(index of the challenger suffix), andk = 0(length of the common prefix between suffixes atiandj). - Loop while
j + k < n. - Case 1:
s.charAt(i + k) == s.charAt(j + k)- The characters match, so extend the common prefix by incrementing
k.
- The characters match, so extend the common prefix by incrementing
- Case 2:
s.charAt(i + k) > s.charAt(j + k)- The challenger suffix
s[j:]is smaller than the current bests[i:]. We can discard not onlys[j:]but also all suffixes starting fromj+1toj+k. So, we advance the challenger pointerjtoj + k + 1and resetkto0.
- The challenger suffix
- Case 3:
s.charAt(i + k) < s.charAt(j + k)- The current best suffix
s[i:]is smaller than the challengers[j:].s[i:]is eliminated. The new best candidate iss[j:]. We updatei = j, advance the challenger toj = i + 1, and resetkto0.
- The current best suffix
- After the loop terminates, the starting index of the last substring is
i. Returns.substring(i).
Walkthrough
We use three integer variables: i, j, and k. i is the starting index of the current best candidate for the last substring. j is the starting index of the challenger substring. k is the offset from i and j, representing the length of the common prefix we have checked so far.
We iterate while j + k is within the bounds of the string. By comparing s.charAt(i + k) and s.charAt(j + k), we decide which candidate to eliminate.
If s.charAt(i + k) > s.charAt(j + k), the challenger s[j:] is smaller. We can prove that all suffixes starting from j to j+k are also smaller than s[i:], so we can safely jump the challenger pointer j to j + k + 1.
If s.charAt(i + k) < s.charAt(j + k), the current best s[i:] is smaller. It gets eliminated, and s[j:] becomes the new best candidate. We update i to j and continue searching for a new challenger from j+1. All suffixes between the old i and j have already lost to s[old_i:] and are therefore also smaller than the new best s[j:].
This process of elimination continues until j scans past the end of the string. The final value of i gives the starting index of the lexicographically last substring.
public String lastSubstring(String s) { int n = s.length(); int i = 0, j = 1, k = 0; while (j + k < n) { if (s.charAt(i + k) == s.charAt(j + k)) { k++; continue; } if (s.charAt(i + k) > s.charAt(j + k)) { // Suffix at j is smaller, so it and its subsequent k suffixes are eliminated. j = j + k + 1; } else { // Suffix at i is smaller, so it's eliminated. j becomes the new candidate. i = j; j = i + 1; } k = 0; } return s.substring(i);}Complexity
Time
O(n) - Although there's a loop within a loop, the pointers `i` and `j` only move forward. The total number of character comparisons is bounded by a linear function of `n`. In each step, either `k` increases, or the sum `i+j` increases. The total advancement of `i`, `j`, and `k` is O(n), making the overall time complexity linear.
Space
O(1) auxiliary space. The algorithm only uses a few integer variables (`i`, `j`, `k`). The space for the final returned substring is O(n) but is not counted as auxiliary space.
Trade-offs
Pros
Highly efficient with an optimal time complexity of O(n).
Uses constant auxiliary space (excluding the space for the output string).
Cons
The logic, especially the pointer updates, is more complex and less intuitive than the brute-force approach.
The proof of correctness is non-trivial.
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); }}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:]class Solution { public: string lastSubstring ( string s ) { int n = s . size (); int i = 0 ; for ( int 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 . substr ( 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.