class Solution:
    def maxNumOfSubstrings(self, s: str) -> list[str]:
        first, last = {}, {}

        # fill up the first and last
        for i, c in enumerate(s):
            if c not in first:
                first[c] = i
            last[c] = i # edge: if only one, start = end

        intervals = []
        # traverse first (parse all letters start idx)
        for c, start in first.items(): 
            # fix the start letter, then extend the length to valid
            current_end = last[c]
            idx = start
            valid = True

            # extend the substring and check the condition
            while idx < current_end:
                idx += 1 
                current_c = s[idx]

                # if start before the front, not valid
                if first[current_c] < start:
                    valid = False
                    break
                
                # if end behind the current_end, extend the current_end
                current_end = max(current_end, last[current_c])

            if valid:
                # update ans
                intervals.append((start, current_end))

        res = []
        intervals.sort(key = lambda x: x[1]) # sort by end (greedy)
        prev_end = -1
        for start, end in intervals:
            if start > prev_end:
                prev_end = end
                res.append(s[start:end+1]) # + 1 for last letter 

        return res