Problem statement

https://binarysearch.com/problems/Concatenated-String-of-Unique-Count/

Solution

Equal to Leetcode 1239. Maximum Length of a Concatenated String with Unique Characters.

Complexity

It is O(2^k) for time and space, where k = len(arr)

Code

class Solution:
    def solve(self, arr):
        arr = [word for word in arr if len(set(word)) == len(word)]
        dp = set([0])
        
        for a in arr:
            dp2 = dp.copy()
            mask = sum(1<<(ord(w) - 97) for w in a)
            for c in dp:
                if mask & c: continue
                dp2.add(mask | c)
            dp = dp2
        
        return max(bin(i).count("1") for i in dp)