Finding the last substring in lexicographical order in O(n) time

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: "abab" Output: "bab" Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

More specifically, I am looking for an accompanying proof/intuition. I can find many solutions, but none provide a proof of their technique and I cannot convince myself.

• What have been your attempts at a solution? Can you come up with an algorithm which does what it is needed, even if a slower one? – dkaeae Aug 20 at 7:26
• Might help: The solution is always a substring ending at the end of the original string, so there are only n possible candidates, not about n(n/2). Maybe that implies you should start looking at the end. – gnasher729 Aug 20 at 14:26
• the answer is going to be an suffix of the string starting from the character with highest up in lexicographical order – Koushik Ghosh Sep 19 at 5:35
• Hint suggests using Suffix array . – Koushik Ghosh Sep 19 at 5:35

Consider a string of 100 million characters with say 100 z’s in between plus a huge number of the characters a to y (and no character lexicographically after z). Find an algorithm that would often give you the correct result in O(n), actually with at most 2n comparisons. Find out why this algorithm doesn’t always run in O(n), then figure out what you can do about it to still run in O(n). For example, if you have a million repetitions of zabcdefabcdef.

Greedily keep track of the lexicographically last character and all characters following it. It will take $$2n$$ comparisons at most as @gnasher suggested.

The rules are as follows where str is the input string:

• Keep track of current best (lexicographically last) string last. Initially it is the first character of str.

• For i in the range [1, length(str)]:

• Let k be an offset equal to 0 initially.

• For j in the range [0, length(last) + 1]:

1. If str[i + k] is less than last[j] or j = length(last) then append str[i, i + k] to last. Set i = i + k + 1 and break this loop.
2. If str[i + k] is greater than last[j] then set last = str[i, i + k]. Set i = i + k + 1 and break this loop.
3. If str[i + k] is equal to last[j] then k++ and continue this loop.
• Return last.

It runs in $$O(n)$$ but may take $$~2n$$ comparisons because we have to scan back through last, although we never scan an index in str more than twice.