Maximum Length of a Concatenated String with Unique Characters LeetCode solution in Python

1
# Runtime: 266 ms (Top 32.10%) | Memory: 14.1 MB (Top 35.69%)
2
class Solution:
3
    def maxLength(self, arr: List[str]) -> int:
4
        ans = 0
5
        count = [0] * 26
6
        counts = []
7
        new_arr = []
8

9
        for string in arr:
10
            flag = True
11
            tmp = [0] * 26
12
            for ch in string:
13
                if tmp[ord(ch) - 97] == True:
14
                    flag = False
15
                    break
16
                else:
17
                    tmp[ord(ch) - 97] = True
18

19
            if flag == False:
20
                continue
21
            counts.append(tmp)
22
            new_arr.append(string)
23

24
        n = len(new_arr)
25

26
        def compatible(a, b):
27
            for i in range(26):
28
                if a[i] == True and b[i] == True:
29
                    return False
30
            return True
31

32
        def addUp(a, b):
33
            for i in range(26):
34
                if b[i] == True:
35
                    a[i] = True
36

37
        def solve(index, count):
38
            if index == n:
39
                return 0
40
            cpy = count.copy()
41
            ch1 = -inf
42
            if compatible(count, counts[index]):
43
                addUp(count, counts[index])
44
                ch1 = solve(index + 1, count) + len(new_arr[index])
45
            ch2 = solve(index + 1, cpy)
46
            ans = max(ch1, ch2)
47
            return ans
48

49
        return solve(0, count)