Welcome to Subscribe On Youtube

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:

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:

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)

All Problems

All Solutions