1239. Maximum Length of a Concatenated String With Unique Characters

Medium
Description

給定一個字串陣列 arr，從中選出子序列（可跳選）並依序串接，使得串接結果中所有字元唯一。回傳滿足條件的最長串接字串長度。

Example:

Input: arr = [“un”,“iq”,“ue”] Output: 4（“uniq” 或 “ique”）

Intuition#

核心思路：回溯法嘗試選或不選每個字串，用 bitmask 追蹤已使用的字元以快速判斷衝突。

  • 每個字串選或不選 → 子集型回溯
  • 需要快速判斷兩組字元是否有交集 → bitmask（26 位表示 a-z）
  • 先過濾掉自身有重複字元的字串

Approaches#

1: 回溯#

  • 概念: 對每個字串做選或不選的決策，用 Set 追蹤已選字元
  • 時間複雜度: O(2^n * m) - n 為陣列長度，m 為字串平均長度
  • 空間複雜度: O(n * m)
class Solution {
    fun maxLength(arr: List<String>): Int {
        var maxLen = 0

        fun backtrack(idx: Int, current: Set<Char>) {
            maxLen = maxOf(maxLen, current.size)
            if (idx == arr.size) return

            for (i in idx until arr.size) {
                val s = arr[i]
                // 檢查自身無重複且與 current 無交集
                if (s.length == s.toSet().size && s.none { it in current }) {
                    backtrack(i + 1, current + s.toSet())
                }
            }
        }

        backtrack(0, emptySet())
        return maxLen
    }
}

⭐2: Bitmask 回溯#

  • 概念: 將每個字串轉為 bitmask，用位元 AND 快速判斷交集，回溯嘗試所有子集
  • 時間複雜度: O(2^n)
  • 空間複雜度: O(n)
class Solution {
    fun maxLength(arr: List<String>): Int {
        // 預處理：將每個字串轉為 bitmask，過濾掉有重複字元的
        val masks = mutableListOf<Pair<Int, Int>>() // (mask, length)
        for (s in arr) {
            var mask = 0
            var valid = true
            for (c in s) {
                val bit = 1 shl (c - 'a')
                if (mask and bit != 0) {
                    valid = false
                    break
                }
                mask = mask or bit
            }
            if (valid) masks.add(mask to s.length)
        }

        var maxLen = 0

        fun backtrack(idx: Int, usedMask: Int, length: Int) {
            maxLen = maxOf(maxLen, length)

            for (i in idx until masks.size) {
                val (mask, len) = masks[i]
                // 位元 AND 檢查無交集
                if (usedMask and mask == 0) {
                    backtrack(i + 1, usedMask or mask, length + len)
                }
            }
        }

        backtrack(0, 0, 0)
        return maxLen
    }
}

🔑 Takeaways#

  • Pattern: 子集型回溯 + bitmask 加速字元衝突判斷
  • 關鍵技巧: 26 個字母用 Int 的 26 位表示，AND == 0 表示無交集，OR 合併已用字元；預先過濾自身有重複的字串減少搜索空間