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

## 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.

## Solutions

Solution 1: Bit Manipulation + State Compression

State compression is used, with a 32-bit number recording the occurrence of letters, and masks storing the strings enumerated before.

The time complexity is $O(2^n + L)$, and the space complexity is $O(2^n)$. Where $n$ and $L$ are the length of the string array and the sum of the lengths of the strings in the array, respectively.

• class Solution {
public int maxLength(List<String> arr) {
int ans = 0;
for (var s : arr) {
for (int i = 0; i < s.length(); ++i) {
int j = s.charAt(i) - 'a';
if (((mask >> j) & 1) == 1) {
break;
}
}
continue;
}
for (int i = 0; i < n; ++i) {
if ((m & mask) == 0) {
ans = Math.max(ans, Integer.bitCount(m | mask));
}
}
}
return ans;
}
}

• class Solution {
public:
int maxLength(vector<string>& arr) {
int ans = 0;
for (auto& s : arr) {
for (auto& c : s) {
int i = c - 'a';
if (mask >> i & 1) {
break;
}
}
continue;
}
for (int i = 0; i < n; ++i) {
if ((m & mask) == 0) {
ans = max(ans, __builtin_popcount(m | mask));
}
}
}
return ans;
}
};

• class Solution:
def maxLength(self, arr: List[str]) -> int:
ans = 0
for s in arr:
for c in s:
i = ord(c) - ord('a')
if mask >> i & 1:
break
continue
if m & mask == 0:
ans = max(ans, (m | mask).bit_count())
return ans


• func maxLength(arr []string) (ans int) {
for _, s := range arr {
for _, c := range s {
i := int(c - 'a')
break
}
}
continue
}
for _, m := range masks[:n] {