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.

題目翻譯

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

解法解析

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

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

程式範例

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);
        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

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

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