763. Partition Labels

 1class Solution:
 2    def partitionLabels(self, s: str) -> List[int]:
 3        # idea:
 4        # for the 26 letters, find out each one's starting and ending: O(n)
 5        # one last traversal from left to right: cut when we have no in-betweens
 6
 7        letters = {}  # [starting idx, ending idx]
 8        for idx, ch in enumerate(s):
 9            if ch not in letters:
10                letters[ch] = [idx, idx]
11            else:
12                letters[ch][1] = idx
13                
14        # print(letters)
15
16        result = []
17        segment = 0
18        unfinished_letter_count = 0
19
20        for idx, ch in enumerate(s):
21            # add current ch, then check unfinished + store to result
22            segment += 1
23            if idx == letters[ch][0]:  # if we see ch the first time
24                unfinished_letter_count += 1
25            if idx == letters[ch][1]:  # if idx is the last occurance of ch
26                unfinished_letter_count -= 1
27
28            if not unfinished_letter_count:  # if all are finished
29                result.append(segment)
30                segment = 0
31            
32            # print(idx, ch, result, segment, unfinished_letter_count)
33
34        if segment:
35            result.append(segment)
36
37        return result