Count Unique Characters of All Substrings of a Given String LeetCode solution in Python

1
class Solution:
2
    def uniqueLetterString(self, s: str) -> int:
3
        ans = 0
4
        idx_recorder = collections.defaultdict(list)
5
        n = len(s)
6

7
        # record the index for every character
8
        # s = "ABCA"
9
        # {
10
        #     "A": [0, 3],
11
        #     "B": [1],
12
        #     "C": [2],
13
        # }
14
        for idx in range(len(s)):
15
            c = s[idx]
16
            idx_recorder[c].append(idx)
17

18
        def helper(idxes):
19
            ans = 0
20

21
            for i in range(len(idxes)):
22
                # Count the number of substring which contain the character without duplicating
23
                # get the left, right value to compute the result.
24
                #
25
                # Take the middle A (idx=3) as example
26
                # s = 'AxxAxxxAxx'
27
                #         -
28
                # left = 3 - 0 = 3
29
                # right = 7 - 3 = 4
30
                #
31
                # The number of substring which contain this A (idx=3) without containing
32
                # other A is 3 * 4 = 12
33

34
                if i == 0:
35
                    # If it is a first one: it means that there is
36
                    # no duplicate character in left
37
                    left = idxes[i] + 1
38
                else:
39
                    left = idxes[i] - idxes[i - 1]
40

41
                if i == len(idxes) - 1:
42
                    # If it is a last one: it means that there is
43
                    # no duplicate character in right side
44
                    right = n - idxes[i]
45
                else:
46
                    right = idxes[i + 1] - idxes[i]
47

48
                ans += left * right
49

50
            return ans
51

52
        ans = 0
53
        for c in idx_recorder:
54
            ans += helper(idx_recorder[c])
55
        return ans