1239. Maximum Length of a Concatenated String with Unique Characters
解題說明
Maximum Length of a Concatenated String with Unique Characters
題目描述：給定字串陣列 arr，從中選取若干字串依次拼接，使得拼接後的字串所有字符均唯一（無重複字符）。求此拼接字串的最大長度。
解題思路（位元遮罩 + 回溯）：
預處理：對每個字串 s，用 26 位整數 mask 記錄其字符集合（bit i 代表第 i 個小寫字母是否出現）。若 s 自身有重複字符（popcount(mask) != s.length()），直接過濾掉。
回溯/DFS：枚舉每個字串「選」或「不選」，維護當前拼接狀態的位元遮罩 curMask：
- 若
masks[i] & curMask == 0（無共用字符）：可選，遞迴進入dfs(i+1, curMask | masks[i])，更新最大長度為popcount(curMask | masks[i])。 - 不論選或不選，都要遞迴到下一個字串。
位元操作 AND 用於快速判斷兩字符集合是否有交集，OR 用於合併，popcount（__builtin_popcount）計算字符總長度。
複雜度分析：陣列長度 n ≤ 16，有效字串最多 16 個，每個選/不選有 2¹⁶ = 65536 種組合，每次操作 O(1)，整體為 O(2^n)。
C++ 解法
複雜度分析
時間複雜度：O(2^n · n) — 每個有效字串可選或不選，共 2^n 個子集；對每個狀態需遍歷剩餘字串，最壞情況為 O(2^n · n)。由於 n ≤ 16，最多 2¹⁶ = 65536 種組合，實際運行速度很快。
空間複雜度：O(n) — 遞迴深度最多 n 層（每次選一個字串往下遞迴），masks 和 lens 陣列大小 O(n)。
虛擬碼
1. For each string s in arr:
a. Compute mask (26-bit) for s.
b. If s has duplicate chars (popcount(mask) != len(s)): skip.
c. Else: add mask and len to lists.
2. dfs(idx=0, curMask=0, curLen=0):
a. ans = max(ans, curLen).
b. For i from idx to end:
- If masks[i] AND curMask == 0:
* dfs(i+1, curMask OR masks[i], curLen + lens[i]).
3. Return ans.其他解法
方法二：迭代式位元遮罩（BFS/DP over subsets）
用集合 dp 儲存所有可達的位元遮罩狀態（初始為 {0}）。對每個字串的 mask，若與 dp 中某個狀態無交集，則將合併結果加入 dp。最後 dp 中 popcount 最大的狀態即為答案。時間 O(2^n · n)，空間 O(2^n)。無遞迴開銷，但需要儲存所有可達狀態，記憶體使用較回溯法高。
方法三：暴力子集枚舉
枚舉所有 2^n 個子集，對每個子集檢查字串拼接後是否有重複字符（用字符計數陣列）。時間 O(2^n · n · L)（L 為平均字串長度），無位元優化，不如方法一和二高效。
方法四：剪枝搜尋
在回溯中加入剪枝：若當前已選字串的長度加上剩餘所有字串的長度 ≤ 目前最優解，直接剪枝。在 n = 16 的測試規模下剪枝效果有限，但對更大輸入有顯著優化。
延伸思考
- 若字符集從 26 個小寫字母擴展到所有 ASCII 可列印字符（約 95 個），26 位整數遮罩不夠用，應如何修改資料結構（如
bitset<128>或兩個 64 位整數）？ - 若改為允許每個字串使用多次（無限次選取），問題如何變化？貪心策略是否有效？
- 此題限制 n ≤ 16 是關鍵，若 n = 30，2³⁰ ≈ 10⁹ 會超時，有沒有基於 meet-in-the-middle 的解法可以將複雜度降至 O(2^(n/2))？