blob: 5d8576e03eaa1a2894fa6dc62bbb4491bfdce8d9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
# 1239. Maximum Length of a Concatenated String with Unique Characters
"""
given an array of strings 'arr'. a string 's' is formed by the concatenation
of subsequence of 'arr', that has unique characters. return the maximum
possible length of 's'. a subsequence is an array that can be derived from
another array by deleting some or no elements without changing the order of
the remaining elements.
"""
class Solution(object):
def maxLength(self, arr):
"""
:type arr: List[str]
:rtype: int
"""
dp = [set()]
for i in arr:
if len(set(i)) < len(i):
continue
i = set(i)
for c in dp[:]:
if i & c:
continue
dp.append(i | c)
return max(len(i) for i in dp)
if __name__ == "__main__":
obj = Solution()
print(obj.maxLength(arr=["un", "iq", "ue"]))
print(obj.maxLength(arr=["cha", "r", "act", "ers"]))
print(obj.maxLength(arr=["abcdefghijklmnopqrstuvwxyz"]))
|