Finding the last substring in lexicographical order in O(n) time
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.