1239. Maximum Length of a Concatenated String with Unique Characters

Problem Link

Description

---

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").

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.

 

Constraints:

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i] contains only lowercase English letters.

Solution

---

Python3

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        A = []
        res = 0
 
        def f(x):
            return ord(x) - ord('a')
 
        for word in arr:
            mask = 0
 
            for x in word:
                if mask & (1 << f(x)): break
                mask |= (1 << f(x))
            else:
                A.append((mask, len(word)))
        
        for mask in range(1, 1 << len(A)):
            curr = 0
            length = 0
 
            for k in range(len(A)):
                if mask & (1 << k) > 0:
                    if curr & A[k][0] == 0:
                        curr |= A[k][0]
                        length += A[k][1]
                    else:
                        break
            else:
                res = max(res, length)
        
        return res