MediumRating 1869
2002. Maximum Product of the Length of Two Palindromic Subsequences
stringdynamic-programmingbacktrackingbit-manipulationbitmask
解題說明
Maximum Product of the Length of Two Palindromic Subsequences
題目描述：
給定一個字串 s，找出兩個不相交的回文子序列，使得它們長度的乘積最大。兩個子序列「不相交」指它們不共用任何索引。
解題思路：
由於 s 的長度最多為 12，可以使用位元遮罩（bitmask）枚舉所有子集：
- 用 bitmask 表示子序列：若第
i位為 1，表示選取s[i]。 - 預處理：對每個 bitmask，判斷它代表的子序列是否為回文，並記錄其長度。
- 枚舉所有不相交的 bitmask 對
(mask1, mask2)，條件為mask1 & mask2 == 0。 - 若兩者都是回文，更新最大乘積。
優化：只需枚舉一個 mask 的所有子集的補集即可，或直接雙重迴圈加判斷。
C++ 解法
複雜度分析
時間複雜度：O(3^n) — 枚舉不相交子集對的總數為 O(3^n)（每個元素有三種狀態：屬於 mask1、mask2、或都不屬於），加上預處理 O(2^n * n)。n <= 12 時可接受。
空間複雜度：O(2^n) — 儲存每個 bitmask 的回文長度。
虛擬碼
1. Precompute for each bitmask (1 to 2^n - 1):
a. Extract subsequence characters
b. Check if palindrome
c. Store length if palindrome, else 0
2. For each bitmask m1 with palLen[m1] > 0:
a. Compute complement = (2^n - 1) XOR m1
b. Enumerate all submasks m2 of complement:
- If palLen[m2] > 0: update ans = max(ans, palLen[m1] * palLen[m2])
3. Return ans其他解法
回溯法（Backtracking）：對每個字元決定放入子序列 1、子序列 2、或都不放。同時維護兩個子序列是否為回文。最壞時間複雜度 O(3^n)，但可透過剪枝加速。
DP + Bitmask O(2^n * n)：先用 DP 對每個 bitmask 計算「最長回文子序列長度」，然後枚舉不相交對。但由於需要的是確切的回文判斷而非最長回文，此法需要適當調整。
延伸思考
- 如果字串長度增加到 20 或更大，O(3^n) 的方法是否仍可行？有什麼替代策略？
- 如何將此問題推廣為 k 個不相交回文子序列的最大乘積？
- 如果要求兩個子序列必須覆蓋字串所有字元（即不允許不屬於任何子序列的字元），問題如何變化？