Last Substring in Lexicographical Order

Last Substring in Lexicographical Order

1. What is this problem about?

The Last Substring in Lexicographical Order coding problem asks you to find the substring of a given string that appears last in alphabetical order. For example, in the string "banana", the lexicographical order of its substrings would include "a", "an", "ana", "anana", "ananan", "b", "ba", "ban", "bana", "banan", "banana", "n", "na", "nan", "nana". The last one alphabetically would be "nana".

2. Why is this asked in interviews?

This "Hard" problem is asked by companies like Microsoft and Amazon to test a candidate's understanding of string comparisons and pointers. While a brute-force approach of generating all substrings and sorting them is O(N²), a linear O(N) solution using two pointers is required for large strings. It evaluates your ability to optimize string searches without using heavy data structures like suffix trees.

3. Algorithmic pattern used

This problem follows the Two Pointers and String interview pattern. We use two pointers, i and j, to compare two candidate substrings. We also use an offset k. We compare s[i+k] and s[j+k]. If they are equal, we increment k. If s[i+k] < s[j+k], then any substring starting at i cannot be the "last," so we move i and reset k. This continues until we've scanned the entire string.

4. Example explanation

String: "ababa".

1. i = 0 (starts with 'a'), j = 1 (starts with 'b').
2. s[0] < s[1], so move i to i + k + 1 = 1. But wait, j is already 1.
3. Compare i = 1 ("b...") and j = 2 ("a..."). s[1] > s[2], so move j.
4. Compare i = 1 ("b...") and j = 3 ("b..."). Now use offset k.
5. s[1+0] == s[3+0]. k = 1.
6. s[1+1] ('a') == s[3+1] ('a'). k = 2.
7. i + k and j + k reach string end. Result: Substring starting at i=1: "baba".

5. Common mistakes candidates make

A common mistake is the O(N²) approach of comparing all suffixes. Another is not handling the case where one pointer "jumps" over the other, leading to redundant comparisons. Correct pointer arithmetic and handling the "offset" k are the most difficult parts of the O(N) implementation.

6. Interview preparation tip

For "Two Pointers, String interview pattern" problems, focus on how to "skip" redundant work. In this problem, if you find that s[i+k] < s[j+k], you don't just move i by 1; you can move it to i+k+1 because no substring starting between i and i+k can beat the one starting at j.