Description
給定字串
s，找出兩個不相交的回文子序列，使它們長度的乘積最大。回傳該最大乘積。（兩個子序列不相交意味著它們不共用任何索引。）
Example:
Input: s = “leetcodecom” Output: 9 （選擇 “ete” 和 “coc”，長度乘積 3 × 3 = 9）
Intuition#
核心思路：字串長度最多 12，可以用 Bitmask 枚舉所有子序列（2^12 = 4096），預計算每個 mask 是否為回文及其長度，再枚舉不相交的兩個 mask 取最大乘積。
- 約束
s.length <= 12暗示 Bitmask 暴力列舉可行 - 第一步：枚舉所有 2^n 個 mask，檢查對應子序列是否為回文，記錄其長度
- 第二步：枚舉所有 mask 對
(m1, m2)，滿足m1 & m2 == 0（不相交），取最大乘積
Approaches#
1: Bitmask Brute Force#
- 概念: 枚舉所有 2^n 子集，過濾回文子序列，再雙重迴圈找不相交的最大乘積
- 時間複雜度:
O(2^n * n + 4^n)- 預處理 O(2^n * n)，枚舉配對 O(4^n)（最壞） - 空間複雜度:
O(2^n)- 儲存每個 mask 的回文長度
class Solution {
fun maxProduct(s: String): Int {
val n = s.length
val total = 1 shl n
val palindromeLen = IntArray(total)
// 預計算每個 mask 對應子序列是否回文及長度
for (mask in 1 until total) {
val subseq = StringBuilder()
for (i in 0 until n) {
if (mask and (1 shl i) != 0) subseq.append(s[i])
}
if (isPalindrome(subseq.toString())) {
palindromeLen[mask] = subseq.length
}
}
var maxProd = 0
for (m1 in 1 until total) {
if (palindromeLen[m1] == 0) continue
for (m2 in m1 + 1 until total) {
if (palindromeLen[m2] == 0) continue
if (m1 and m2 == 0) {
maxProd = maxOf(maxProd, palindromeLen[m1] * palindromeLen[m2])
}
}
}
return maxProd
}
private fun isPalindrome(s: String): Boolean {
var l = 0; var r = s.length - 1
while (l < r) {
if (s[l] != s[r]) return false
l++; r--
}
return true
}
}⭐2: Bitmask + Subset Enumeration 優化#
- 概念: 對每個回文 mask
m1，只枚舉其補集complement的子集作為m2，減少無效配對 - 時間複雜度:
O(3^n)- 枚舉子集的複雜度（每個 bit 有三種狀態：屬於 m1、屬於 m2、不屬於任一） - 空間複雜度:
O(2^n)- 儲存每個 mask 的回文長度
class Solution {
fun maxProduct(s: String): Int {
val n = s.length
val total = 1 shl n
val palindromeLen = IntArray(total)
for (mask in 1 until total) {
val subseq = StringBuilder()
for (i in 0 until n) {
if (mask and (1 shl i) != 0) subseq.append(s[i])
}
val str = subseq.toString()
var l = 0; var r = str.length - 1
var isPalin = true
while (l < r) {
if (str[l] != str[r]) { isPalin = false; break }
l++; r--
}
if (isPalin) palindromeLen[mask] = str.length
}
var maxProd = 0
for (m1 in 1 until total) {
if (palindromeLen[m1] == 0) continue
// 枚舉 m1 補集的所有子集
val complement = (total - 1) xor m1
var m2 = complement
while (m2 > 0) {
if (palindromeLen[m2] > 0) {
maxProd = maxOf(maxProd, palindromeLen[m1] * palindromeLen[m2])
}
m2 = (m2 - 1) and complement
}
}
return maxProd
}
}子集枚舉技巧
m2 = (m2 - 1) & complement可以高效地遍歷complement的所有非空子集。這是 Bitmask DP 中常見的優化手法。
🔑 Takeaways#
- Pattern: 小規模字串（n <= 12~20）-> Bitmask 枚舉所有子集
- 關鍵技巧: 補集子集枚舉
m2 = (m2-1) & complement將 O(4^n) 優化到 O(3^n)；Bitmask 常用於需要枚舉所有子集組合的問題