aboutsummaryrefslogtreecommitdiff
path: root/max_len_concat_str.py
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"]))