[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

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

This problem is kind of knapsack problem.  For each sub-string, we can pick it if it does not introduce duplicated character or not pick it and use the rest sub-string to form a longer string.

Time Complexity = O ( N ** 2 ).  N = len(arr)

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        # filter sub-string with duplicated characters
        wordsets = [set(w) for w in arr if len(set(w)) == len(w)]
        
        def helper(start, mask):
            if start >= len(wordsets):
                return len(mask)
            
            # don't pick current sub-string if it introduces duplicated characters
            if mask & wordsets[start]:
                return helper(start + 1, mask)
            
            picked = helper(start + 1, mask | wordsets[start])
            notPicked = helper(start + 1, mask)
            
            return picked if picked > notPicked else notPicked
        
        return helper(0, set())