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

Constraints:

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

Hint 1:

You can try all combinations and keep mask of characters you have.

Hint 2:

You can use DP.

### 解法解析

#### 程式範例

##### Python

Runtime Best

``````class Solution:
def maxLength(self, arr: List[str]) -> int:
def max_len_of_merged_word(words):
largest, M = 0, len(words)
for i in range(M):
word_set_1 = set(words[i])
size = len(words[i])
for j in range(M):
if j == i:
continue
word_set_2 = set(words[j])
if word_set_1.isdisjoint(word_set_2):
size += len(words[j])
word_set_1 = word_set_1.union(word_set_2)
largest = max(largest, size)
return largest

strs = [arr[i]
for i in range(len(arr)) if len(arr[i]) == len(set(arr[i]))]
return max(
max_len_of_merged_word(strs),
max_len_of_merged_word(sorted(strs, reverse=True)))
``````

Memory Best

``````class Solution:
def maxLength(self, arr: List[str]) -> int:
return self.helper('', arr, 0)

def helper(self, curr, arr, idx):
res = len(curr)
if idx >= len(arr):
return res

for i in range(idx, len(arr)):
if not set(curr) & set(arr[i]) and (len(arr[i]) == len(set(arr[i]))):
res = max(res, self.helper(curr + arr[i], arr, i + 1))
return res
``````
##### JavaScript
``````/**
* @param {string[]} arr
* @return {number}
*/
var maxLength = function (arr) {
let optSet = new Set();
for (let word of arr) optimize(optSet, word);
optArr = [...optSet];
return dfs(optArr, 0, 0);
};

const optimize = (optSet, word) => {
let charBitSet = 0;
for (let c of word) {
const mask = 1 << (c.charCodeAt() - 97);
}

};

const dfs = (optArr, pos, res) => {
const oldChars = res & ((1 << 26) - 1),
oldLen = res >> 26;
let best = oldLen;

for (let i = pos; i < optArr.length; i++) {
const newChars = optArr[i] & ((1 << 26) - 1),
newLen = optArr[i] >> 26;

if (newChars & oldChars) continue;

const newRes = oldChars + newChars + ((oldLen + newLen) << 26);
best = Math.max(best, dfs(optArr, i + 1, newRes));
}
return best;
};
``````
##### Go
``````func maxLength(arr []string) int {
c := []uint32{}
max := 0
for _, s := range arr {
for _, c := range s {
}
continue
}
}
dfs(c, 0, 0, &max)
return max
}

func dfs(c []uint32, index int, mask uint32, max *int) {
for i := index; i < len(c); i++ {
}
}
return
}

func Max(a, b int) int {
if a > b {
return a
}
return b
}
``````
##### Swift
``````class Solution {
private func isUnique(_ str: String) -> Bool {
let set = Set<Character>(str)
return set.count == str.count
}

func maxLength(_ arr: [String]) -> Int {
var combos = [String]()
var maximum = 0

combos.append("")

for s in arr {
for c in combos {
let str = c + s
if isUnique(str) {
combos.append(str)
maximum = max(maximum, str.count)
}
}
}

return maximum
}
}
``````
##### Kotlin
``````class Solution {
fun getMaxLength(
arr: List<String>,
charsInstring: Array<Int>,
uniqueLength: Int,
i: Int,
maxLengthTillNow: Int
): Int {
if (i >= arr.size) return maxLengthTillNow
var maxLength = 0
if (charsInstring[i] != -1 && charsInstring[i] and uniqueLength == 0) {
var includeLength =
getMaxLength(
arr,
charsInstring,
uniqueLength or charsInstring[i],
i + 1,
maxLengthTillNow + arr[i].length
)
maxLength = includeLength
}
var excludeLength = getMaxLength(arr, charsInstring, uniqueLength, i + 1, maxLengthTillNow)
maxLength = maxOf(maxLength, excludeLength)
return maxLength
}

fun maxLength(arr: List<String>): Int {
val charsInstring: Array<Int> = Array(arr.size) { 0 }
arr.forEachIndexed { index, word ->
var number = 0
var unique = true
word.forEach {
if (number and (1 shl (it - 'a')) != 0) {
unique = false
}
number = number or (1 shl (it - 'a'))
}

if (unique == false) {
charsInstring[index] = -1
} else {
charsInstring[index] = number
}
}
return getMaxLength(arr, charsInstring, 0, 0, 0)
}
}
``````