# LeetCode Solution, Medium, 1239. Maximum Length of a Concatenated String with Unique Characters

# [1239. Maximum Length of a Concatenated String with Unique Characters](https://leetcode.com/problems/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.

#### 題目翻譯

給一個 list 參數 `arr`，其中元素都是字串。要從中找出最長的字串組合。其中這個組合要符合的條件，就是其中的元素需要是唯一的字母。

### 解法解析

大部分的解法，會用到位元運算子 `<<`、`&`、`>>`。有的則是單純的使用演算法比對長度的方式。個人覺得最漂亮的方式是 Swift 的解法。

使用兩個迴圈處理做 Dynamic programming，第一層去遍歷 `arr` 的元素，去跟另一層迴圈遍歷的 list `combos` 做判斷。如果 `arr` 和 `combos` 遍歷的元素相加後，是唯一的話，則儲存到 `combos`，並且跟最大值最比較。

#### 程式範例

##### Python

Runtime Best
```python
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
```python
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

```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);
        if (charBitSet & mask) return;
        charBitSet += mask;
    }

    optSet.add(charBitSet + (word.length << 26));
};

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

```go
func maxLength(arr []string) int {
	c := []uint32{}
	max := 0
	for _, s := range arr {
		var mask uint32
		for _, c := range s {
			mask = mask | 1<<(c-'a')
		}
		if len(s) != bits.OnesCount32(mask) {
			continue
		}
		c = append(c, mask)
	}
	dfs(c, 0, 0, &max)
	return max
}

func dfs(c []uint32, index int, mask uint32, max *int) {
	*max = Max(*max, bits.OnesCount32(mask))
	for i := index; i < len(c); i++ {
		if mask&c[i] == 0 {
			dfs(c, i+1, mask|c[i], max)
		}
	}
	return
}

func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
```

##### Swift

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

```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)
    }
}
```