Assume that the answer is a sub-string from index i to j. If you add the character at index j+1 you get a better answer.

The answer is always a suffix of the given string.

Since the limits are high, we need an efficient data structure.

Use suffix array.