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 <= 12sconsists of lowercase English letters only.
Similar Questions:
- Valid Palindrome (Easy)
- Longest Palindromic Subsequence (Medium)
- Maximum Product of the Length of Two Palindromic Substrings (Hard)
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 )
// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/
// Author: github.com/lzl124631x
// 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;
}
};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]`
)
// OJ: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/
// Author: github.com/lzl124631x
// 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;
}
};