Maximum Product of the Length of Two Palindromic Subsequences
Medium · Backtracking · Explanation and code example
Bit Mask + LPS (Optimal)
How it works
We can further optimize by computing the LPS directly on the original string while using the mask to skip characters that belong to the first subsequence. This avoids creating new strings and reduces overhead. We also validate palindromes efficiently using two pointers with mask-based skipping.
Steps
- For each bitmask, use a two-pointer approach to check if the selected characters form a palindrome and compute its length.
- If it is a palindrome, run the LPS algorithm on the original string, but skip indices that are set in the mask.
- Reset the DP array appropriately before each LPS computation.
- Track and return the maximum product.
Complexity
- Time complexity:
O(n ^ 2 * 2 ^ n) - Space complexity:
O(n)
Things to watch for
Allowing Overlapping Characters Between Subsequences
The two palindromic subsequences must be disjoint, meaning they cannot share any character. When using bitmasks, ensure that (mask1 & mask2) == 0 before considering a pair. Forgetting this check leads to invalid solutions where the same character is counted in both subsequences.
Not Validating Palindrome Before Computing Product
When iterating through bitmasks, some masks represent subsequences that are not palindromes. Computing the product of lengths without first verifying that both subsequences are actually palindromes leads to incorrect maximum values.
Inefficient Palindrome Checking in Tight Loops
Constructing new strings for each subsequence and then checking if they are palindromes is expensive. For optimal solutions, use two-pointer validation directly on the original string with mask-based index skipping to avoid repeated string allocations inside the exponential loop.
Python code example
from typing import List
class Solution:
def longestPalindromeSubseq(self, s: str, mask: int, dp: List[int]) -> int:
n = len(s)
for i in range(n - 1, -1, -1):
if (mask & (1 << i)) != 0:
continue
prev = 0
for j in range(i + 1, n):
tmp = dp[j]
if (mask & (1 << j)) == 0 and s[i] == s[j]:
dp[j] = 2 + prev
else:
dp[j] = max(dp[j - 1], dp[j])
prev = tmp
return dp[-1]
def maxProduct(self, s: str) -> int:
n = len(s)
res = 0
dp = [1] * n
for i in range(1, 1 << n):
m1 = self.palsize(s, i)
if m1 == 0:
continue
for j in range(n):
if (i & (1 << j)) == 0:
dp[j] = 1
else:
dp[j] = 0
m2 = self.longestPalindromeSubseq(s, i, dp)
res = max(res, m1 * m2)
return res
def palsize(self, s: str, mask: int) -> int:
i, j = 0, len(s) - 1
res = 0
while i <= j:
if (mask & (1 << i)) == 0:
i += 1
elif (mask & (1 << j)) == 0:
j -= 1
else:
if s[i] != s[j]:
return 0
res += 1 if i == j else 2
i += 1
j -= 1
return res
C++ code example
class Solution {
public:
int longestPalindromeSubseq(string& s, int mask, vector<int>& dp) {
int n = s.length();
for (int i = n - 1; i >= 0; i--) {
if ((mask & (1 << i)) != 0) continue;
int prev = 0;
for (int j = i + 1; j < n; j++) {
int tmp = dp[j];
if ((mask & (1 << j)) == 0 && s[i] == s[j]) {
dp[j] = 2 + prev;
} else {
dp[j] = max(dp[j - 1], dp[j]);
}
prev = tmp;
}
}
return dp[n - 1];
}
int maxProduct(string s) {
int n = s.length();
int res = 0;
vector<int> dp(n, 1);
for (int i = 1; i < (1 << n); i++) {
int m1 = palsize(s, i);
if (m1 == 0) continue;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) {
dp[j] = 1;
} else {
dp[j] = 0;
}
}
int m2 = longestPalindromeSubseq(s, i, dp);
res = max(res, m1 * m2);
}
return res;
}
int palsize(string& s, int mask) {
int i = 0, j = s.length() - 1;
int res = 0;
while (i <= j) {
if ((mask & (1 << i)) == 0) i++;
else if ((mask & (1 << j)) == 0) j--;
else {
if (s[i] != s[j]) return 0;
res += (i == j) ? 1 : 2;
i++;
j--;
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.