Formatted question description: https://leetcode.ca/all/2002.html

# 2002. Maximum Product of the Length of Two Palindromic Subsequences (Medium)

Given a string `s`

, find two **disjoint palindromic subsequences** of `s`

such that the **product** of their lengths is **maximized**. The two subsequences are **disjoint** if they do not both pick a character at the same index.

Return *the maximum possible product of the lengths of the two palindromic subsequences*.

A **subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is **palindromic** if it reads the same forward and backward.

**Example 1:**

Input:s = "leetcodecom"Output:9Explanation: An optimal solution is to choose "ete" for the 1^{st}subsequence and "cdc" for the 2^{nd}subsequence. The product of their lengths is: 3 * 3 = 9.

**Example 2:**

Input:s = "bb"Output:1Explanation: An optimal solution is to choose "b" (the first character) for the 1^{st}subsequence and "b" (the second character) for the 2^{nd}subsequence. The product of their lengths is: 1 * 1 = 1.

**Example 3:**

Input:s = "accbcaxxcxx"Output:25Explanation: An optimal solution is to choose "accca" for the 1^{st}subsequence and "xxcxx" for the 2^{nd}subsequence. The product of their lengths is: 5 * 5 = 25.

**Constraints:**

`2 <= s.length <= 12`

`s`

consists of lowercase English letters only.

**Similar Questions**:

- Valid Palindrome (Easy)
- Longest Palindromic Subsequence (Medium)
- Maximum Product of the Length of Two Palindromic Substrings (Hard)

## Solution 1. Bitmask DP

Let `dp[mask]`

be the length of the longest palindromic subsequence within a subsequence represented by `mask`

.

The answer is `max( dp[m] * dp[(1 << N) - 1 - m] | 1 <= m < 1 << N )`

. (`(1 << N) - 1 - m)`

is the complement subset of `m`

).

For `dp[m]`

, we can brute-forcely enumerate each of its subset, and compute the maximum length of its palindromic subsets.

```
dp[m] = max( bitcount( sub ) | `sub` is a subset of `m`, and `sub` forms a palindrome )
```

```
// Time: O(N * 2^N + 3^N)
// Space: O(2^N)
class Solution {
bool isPalindrome(string &s, int mask) {
vector<int> index;
for (int i = 0; mask; mask >>= 1, ++i) {
if (mask & 1) index.push_back(i);
}
for (int i = 0, j = index.size() - 1; i < j; ++i, --j) {
if (s[index[i]] != s[index[j]]) return false;
}
return true;
}
public:
int maxProduct(string s) {
int N = s.size();
vector<int> dp(1 << N), pal(1 << N);
for (int m = 1; m < 1 << N; ++m) {
pal[m] = isPalindrome(s, m);
}
for (int m = 1; m < 1 << N; ++m) { // `m` is a subset of all the characters
for (int sub = m; sub; sub = (sub - 1) & m) { // `sub` is a subset of `m`
if (pal[sub]) dp[m] = max(dp[m], __builtin_popcount(sub)); // if this subset forms a palindrome, update the maximum length
}
}
int ans = 0;
for (int m = 1; m < 1 << N; ++m) {
ans = max(ans, dp[m] * dp[(1 << N) - 1 - m]);
}
return ans;
}
};
```

## Solution 2. Bitmask DP

In Solution 1, filling the `pal`

array takes `O(N * 2^N)`

time. We can reduce the time to `O(2^N)`

using DP.

```
pal[m] = s[lb] == s[hb] && pal[x]
where `lb` and `hb` are the indexes of the lowest and highest bits of `m`, respectively,
and `x` equals `m` removing the lowest and highest bits.
```

```
vector<bool> pal(1 << N);
pal[0] = 1;
for (int m = 1; m < 1 << N; ++m) {
int lb = __builtin_ctz(m & -m), hb = 31 - __builtin_clz(m);
pal[m] = s[lb] == s[hb] && pal[m & ~(1 << lb) & ~(1 << hb)];
}
```

Using the same DP idea, we can reduce the time complexity for filling the `dp`

array from `O(3^N)`

to `O(2^N)`

, and we don’t even need the `pal`

array.

```
// if `m` has only a single bit 1
dp[m] = 1
// otherwise
dp[m] = max(
dp[m - (1 << lb)], // if we exclude `s[lb]`
dp[m - (1 << hb)], // if we exclude `s[hb]`
dp[m - (1 << lb) - (1 << hb)] + (s[lb] == s[hb] ? 2 : 0) // If we exclude both `s[lb]` and `s[hb]` and plus 2 if `s[lb] == s[hb]`
)
```

```
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
int maxProduct(string s) {
int N = s.size();
vector<int> dp(1 << N);
for (int m = 1; m < 1 << N; ++m) {
if (__builtin_popcount(m) == 1) dp[m] = 1;
else {
int lb = __builtin_ctz(m & -m), hb = 31 - __builtin_clz(m);
dp[m] = max({ dp[m - (1 << lb)], dp[m - (1 << hb)], dp[m - (1 << lb) - (1 << hb)] + (s[lb] == s[hb] ? 2 : 0) });
}
}
int ans = 0;
for (int m = 1; m < 1 << N; ++m) {
ans = max(ans, dp[m] * dp[(1 << N) - 1 - m]);
}
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/discuss/1458788/C%2B%2B-DP-from-O(3N)-to-O(2N)