Problem statement

https://leetcode.com/problems/last-substring-in-lexicographical-order/

Solution 1

We can construct suffix array and then just take the biggest suffix.

Complexity

Time complexity is $O(n\log^2 n)$ using this realization of algorithm, space complexity is $O(n)$.

Code

class Solution:
    def lastSubstring(self, s) :
        def ranks(l):
            index = {v: i for i, v in enumerate(sorted(set(l)))}
            return [index[v] for v in l]

        def suffixArray(s):
            line = ranks(s)
            n, k, ans, sa = len(s), 1, [line], [0]*len(s)
            while max(line) < n - 1:  #k < n - 1 without optimization
                line = ranks(list(zip_longest(line, islice(line, k, None), fillvalue=-1)))
                ans, k = ans + [line], k << 1
            for i, k in enumerate(ans[-1]): sa[k] = i
            return ans, sa
        
        return s[suffixArray(s)[1][-1]:]

Remark

There is in fact $O(n)$ time complexity solution with two points technique, because we need only the biggest suffix, not all of them.