1520. Maximum Number of Non Overlapping Substrings (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maxNumOfSubstrings(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        h, result = {}, []
        for i, c in enumerate(s):
            if c not in h:
                h[c] = [i, i]
            else:
                h[c][1] = i
        for k1 in h:
            for k2 in h:
                if k1 != k2:
                    v1, v2 = h[k1], h[k2]
                    if k1 in s[v2[0] : v2[1]] and k2 in s[v1[0] : v1[1]]:
                        h[k1] = h[k2] = [min(v1[0], v2[0]), max(v1[1], v2[1])]
        subs = sorted(h.values(), key = lambda x: x[1])
        start = -1
        for l, r in subs:
            if l > start:
                result.append(s[l: r + 1])
                start = r
        return result