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

'''
You are given an array of strings arr. A string s is formed by the concatenation of a 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.

Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.

Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
'''

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        subs = [""]
        prev_max = 0

        for word in arr:
            for sub_word in subs:
                new_sub = sub_word+word
                # skip if concatenated substitution is unique 
                if len(new_sub)!=len(set(new_sub)):
                    continue
                subs.append(new_sub)
                prev_max = max(prev_max, len(new_sub))
        return prev_max