題目描述:
給定一個字串 s,找出兩個不相交的回文子序列,使得它們長度的乘積最大。兩個子序列「不相交」指它們不共用任何索引。
解題思路:
由於 s 的長度最多為 12,可以使用位元遮罩(bitmask)枚舉所有子集:
i 位為 1,表示選取 s[i]。(mask1, mask2),條件為 mask1 & mask2 == 0。優化:只需枚舉一個 mask 的所有子集的補集即可,或直接雙重迴圈加判斷。
時間複雜度: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 計算「最長回文子序列長度」,然後枚舉不相交對。但由於需要的是確切的回文判斷而非最長回文,此法需要適當調整。