Maximum Product Of The Length Of Two Palindromic Subsequences - Leetcode Solution

Problem statement:

Given a string s, you need to find the maximum product of the lengths of two palindromic subsequences in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A string is palindromic if it reads the same from left to right and from right to left.

Solution:

Approach:

The brute force approach to find palindromic subsequences of a given string would be to generate all possible subsequences of the string and then check if those are palindromes or not. However, this approach would take exponential time to run.

A more efficient approach would be to use dynamic programming. We can consider the longest palindromic subsequence of the string for each prefix and suffix separately.

For each index of the string, we can consider two cases:

1. We include that index in the first palindromic subsequence and not in the second.

2. We include that index in the second palindromic subsequence and not in the first.

We can store the longest palindromic subsequence for each prefix and suffix separately in two arrays. Let dp1[i] be the length of the longest palindromic subsequence of the prefix s[0:i] and dp2[i] be the length of the longest palindromic subsequence of the suffix s[i:n] (where n is the length of the string s). Since we are considering only palindromic subsequences, we can consider only the characters in the prefix or suffix that occur an even number of times.

We can use a similar approach to find the longest palindromic subsequence for each substring. We can consider all possible combinations of suffix and prefix such that the two substrings do not overlap. We can then take the product of the length of the longest palindromic subsequence of the corresponding prefixes and suffixes.

Code:

Here is the code for the solution:

class Solution { public: int maxProduct(string s) { int n = s.size(); vector<int> dp1(1 << n), dp2(1 << n); for (int mask = 0; mask < (1 << n); mask++) { string t = ""; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { t += s[i]; } } dp1[mask] = longestPalindromicSubsequence(t); reverse(t.begin(), t.end()); dp2[mask] = longestPalindromicSubsequence(t); } int ans = 0; for (int mask1 = 0; mask1 < (1 << n); mask1++) { if (dp1[mask1] == 0) continue; for (int mask2 = 0; mask2 < (1 << n); mask2++) { if (dp2[mask2] == 0) continue; if ((mask1 & mask2) == 0) { ans = max(ans, dp1[mask1] * dp2[mask2]); } } } return ans; }

int longestPalindromicSubsequence(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

};

Time Complexity:

The time complexity of the solution is O(3^n) because we are generating all possible subsequences of the string in the worst case. However, in practice, the time complexity is much smaller because we are considering only palindromic subsequences and we are not generating all possible subsequences.

Space Complexity:

The space complexity of the solution is O(2^n) because we are storing the longest palindromic subsequence for each prefix and suffix separately in two arrays of size 2^n.

1