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: 9
Explanation: An optimal solution is to choose "ete" for the 1st subsequence and "cdc" for the 2nd subsequence.
The product of their lengths is: 3 * 3 = 9.


Example 2:

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


Example 3:

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


Constraints:

• 2 <= s.length <= 12
• s consists of lowercase English letters only.

Similar Questions:

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, 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;
}
};


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 = 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)