Maximum Number of Non-Overlapping Substrings LeetCode solution in Python

1
from collections import defaultdict
2

3

4
class Solution:
5
    def maxNumOfSubstrings(self, s: str) -> List[str]:
6
        st = defaultdict(lambda: -1)
7
        ed = defaultdict(int)
8
        for i, c in enumerate(s):
9
            if st[c] == -1:
10
                st[c] = i
11
                ed[c] = i
12
            else:
13
                ed[c] = i
14
        ints = []
15
        for c in set(s):
16
            b, e = st[c], ed[c]
17
            i = b
18
            while i <= e and b == st[c]:
19
                b = min(b, st[s[i]])
20
                e = max(e, ed[s[i]])
21
                i += 1
22
            if b == st[c]:
23
                ints.append((b, e))
24
        ints.sort(key=lambda e: e[1])
25
        res = []
26
        prev = -1
27
        for i in range(len(ints)):
28
            j, k = ints[i]
29
            if j > prev:
30
                res.append(s[j : k + 1])
31
                prev = k
32
        return res