# 1239. Maximum Length of a Concatenated String with Unique Characters

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

# Solution

Approach 1: enumerate all combinations.

# Code (Python)

Approach 1:

    def maxLength(self, words: List[str]) -> int:
        # idea: enumerate all combinations, but append those to a long, long list (see Combinations problems)
        # can also use bitmaps: bitmap_so_far | ord(letter) - ord('a')
        concated = [set()]
        for word in words:
            # ignore words with dup chars in itself
            if len(set(word)) != len(word):
                continue
            # trick: use a copy of concated to do the iteration while appending to it
            for concat in (_ for _ in concated): 
                if concat & set(word):
                    continue
                concated.append(concat | set(word))
        return max(map(len, concated))

# Code (C++)

Approach 1:

Approach 2: