Maximum Product of the Length of Two Palindromic Subsequences Python/Java solution

Implementations in Python, Java, C++, or JavaScript typically enumerate all bitmasks from 0 to 2^n - 1, check whether the mask forms a palindrome, and store its length. Then iterate through submasks of the unused indices to compute the maximum product of two palindromic subsequences.

What is the best approach for Maximum Product of the Length of Two Palindromic Subsequences?

The most efficient approach uses bitmasking to represent subsequences and precomputes which masks form palindromes. For each valid mask, iterate through submasks of the remaining characters to ensure the second subsequence is disjoint. This reduces the search to about O(3^n) states with O(2^n) memory, which works well for n ≤ 12.

Is Maximum Product of the Length of Two Palindromic Subsequences asked at Google/Amazon/Meta?

Palindrome subsequence and bitmask enumeration problems commonly appear in interviews at companies like Google, Amazon, and Meta. Variants that combine subsequences, bitmask DP, and palindrome checks are frequently used to test combinatorial optimization skills.

What data structure is used in Maximum Product of the Length of Two Palindromic Subsequences?

The main structure is a bitmask representing which characters are included in a subsequence. Arrays or hash maps store the palindrome length for each mask. Bit operations such as AND and submask iteration ensure the two subsequences remain disjoint.

What is the time complexity of Maximum Product of the Length of Two Palindromic Subsequences?

The optimized solution runs in O(n * 2^n + 3^n) time. The first part checks whether each mask forms a palindrome, and the second part enumerates submasks of the remaining characters to find the best disjoint partner subsequence. Space complexity is O(2^n) to store palindrome lengths.

Description Hints 2 Solution Video 16:47

2002. Maximum Product of the Length of Two Palindromic Subsequences

Q: Is Maximum Product of the Length of Two Palindromic Subsequences easy or hard?

The problem is rated Medium on LeetCode with an acceptance rate around 62%. The challenge comes from recognizing that the string length is small and that subsequences can be efficiently represented using bitmasks combined with subset enumeration.

Q: How to solve Maximum Product of the Length of Two Palindromic Subsequences in O(n)?

An O(n) solution does not exist because the problem requires exploring subsequences. The best known approach uses subset enumeration with bitmasks, giving roughly O(3^n) time. Since the input size is small (n ≤ 12), this exponential technique remains practical.

Medium63.0% acceptance2 companies

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 1^st subsequence and "cdc" for the 2^nd 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 1^st subsequence and "b" (the second character) for the 2^nd 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 1^st subsequence and "xxcxx" for the 2^nd subsequence.
The product of their lengths is: 5 * 5 = 25.

Constraints:

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

Asked at 2 companies

Ascend

Google

Topics

Hints open one at a time

Hint 1

Could you generate all possible pairs of disjoint subsequences?

Hint 2

Could you find the maximum length palindrome in each subsequence for a pair of disjoint subsequences?

16:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution