LeetCode 2002: Maximum Product of the Length of Two Palindromic Subsequences Solution

Master LeetCode problem 2002 (Maximum Product of the Length of Two Palindromic Subsequences), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2002. Maximum Product of the Length of Two Palindromic Subsequences

Medium

String Dynamic Programming Backtracking Bit Manipulation Bitmask

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming to generate all possible palindromic subsequences of the input string s. We can then iterate through all pairs of palindromic subsequences and calculate their product of lengths to find the maximum possible product.

Generate all palindromic subsequences of s using dynamic programming.
Iterate through all pairs of palindromic subsequences and calculate their product of lengths.
Keep track of the maximum product found.

Time Complexity

Let n be the length of the input string s. Generating all palindromic subsequences takes O(3^n) time complexity. Iterating through all pairs of palindromic subsequences takes O(n^2) time complexity. Therefore, the overall time complexity is O(3^n + n^2).

Space Complexity

The space complexity for generating all palindromic subsequences is O(3^n) due to the number of subsequences generated. The space complexity for storing the palindromic subsequences is O(2^n) as we only need to store the length of each subsequence.

Solution Code

class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        int[] palindromes = new int[1 << n];

        for (int i = 0; i < (1 << n); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    sb.append(s.charAt(j));
                }
            }
            if (isPalindrome(sb.toString())) {
                palindromes[i] = sb.length();
            }
        }

        int maxProduct = 0;
        for (int i = 0; i < (1 << n); i++) {
            for (int j = i + 1; j < (1 << n); j++) {
                if ((i & j) == 0) {
                    maxProduct = Math.max(maxProduct, palindromes[i] * palindromes[j]);
                }
            }
        }

        return maxProduct;
    }

    private boolean isPalindrome(String str) {
        int i = 0, j = str.length() - 1;
        while (i < j) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2002 (Maximum Product of the Length of Two Palindromic Subsequences)?

This page provides optimized solutions for LeetCode problem 2002 (Maximum Product of the Length of Two Palindromic Subsequences) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2002 (Maximum Product of the Length of Two Palindromic Subsequences)?

The time complexity for LeetCode 2002 (Maximum Product of the Length of Two Palindromic Subsequences) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2002 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2002 in Java, C++, or Python.

Back to LeetCode Solutions