[Leetcode]1520. Maximum Number of Non-Overlapping Substrings

Given a string s of lowercase letters, you need to find the maximum number of non-emptysubstrings of s that meet the following conditions:
The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.
Notice that you can return the substrings in any order.

Example 1:
Input: s = "adefaddaccc" Output: ["e","f","ccc"]
Example 2:
Input: s = "abbaccd" Output: ["d","bb","cc"]

This is actually very similar to Find maximum meetings in one room – we can find the boundaries for all substrings and when we try to find the as many as possible substrings, it’s exactly the same as finding the largest number of meetings (substrings) for one room (the substrings do not overlap).

The following solution is from inspired by @bobby569.

class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        dic = {c: [s.index(c), s.rindex(c)+1] for c in set(s)}
        substr = []
        for c in set(s):
            l = dic[c][0]
            r = dic[c][1]
            l0,r0 = float('inf'),float('-inf')
            while True:
                t = set(s[l:r])
                for k in t:
                    l0 = min(l0, dic[k][0])
                    r0 = max(r0, dic[k][1])
                if l==l0 and r==r0:
                    break
                l, r = l0, r0
            substr.append([l, r])
        # Find maximum meetings in one room
        substr.sort(key=lambda x: x[1])
        res, last = [], 0
        for b, e in substr:
            if b >= last:
                res.append(s[b:e])
                last = e
        return res