Last Substring in Lexicographical Order

Problem Id: 1163 Difficulty: Hard


Intuition

Solution


class Solution:
    def lastSubstring(self, s: str) -> str:
        chars = set(s)
        if len(chars) == 1:
            return s
        start = sorted(chars, reverse=True)[0]
        possibles = []
        for i, c in enumerate(s):
            if c == start:
                possibles.append([i, i])
        while len(possibles) > 1:
            cs = []
            tmp = []
            for i, j in possibles:
                if j + 1 >= len(s):
                    continue
                cs.append(s[j + 1])
            m = max(cs)
            for i, j in possibles:
                if j + 1 >= len(s):
                    continue
                if s[j + 1] == m:
                    tmp.append([i, j + 1])
            possibles = tmp
        return s[possibles[0][0]:]