Problem statement

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

Solution

Iterate through words and for each word keep bitmask. Keep set of all reacheble masks.

Complexity

It is O(2^k) for time, where k = len(arr), because there can be only this is number of options (it is not O(2^26), because not all masks will be used. Space is O(2^k).

Code

class Solution:
    def maxLength(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(i.bit_count() for i in dp)