Maximum Product of the Length of Two Palindromic Subsequences - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: Given a string s, choose two disjoint subsequences such that both are palindromes and the product of their lengths is maximized. The subsequences cannot reuse the same character index.
Approach 1: Brute Force with Bitmasking (O(n * 2^n + 4^n) time, O(2^n) space)
Represent every subsequence using a bitmask of length n. Iterate through all 2^n masks and build the subsequence by checking which bits are set. For each mask, verify whether the subsequence forms a palindrome using a two‑pointer check. Store the length for valid palindromes. Then compare every pair of masks and ensure they are disjoint using (mask1 & mask2) == 0. If both represent palindromes, update the maximum product of their lengths. This method demonstrates the core idea but becomes expensive due to checking every mask pair.
Approach 2: Bitmask Enumeration with Submask Optimization (O(n * 2^n + 3^n) time, O(2^n) space)
Still enumerate all subsequences using bitmasks, but store palindrome lengths in an array pal[mask]. For each mask that forms a palindrome, compute the complement mask representing unused indices. Instead of checking all masks again, iterate through only the submasks of the complement. This ensures both subsequences remain disjoint. The submask iteration reduces pair exploration to roughly 3^n states instead of 4^n. Bit operations make checks extremely fast and work well because the constraint on n is small.
Approach 3: Dynamic Programming with State Representation (O(n * 2^n + 3^n) time, O(2^n) space)
Use a DP-style state where each mask represents a subsequence. Precompute whether a mask forms a palindrome by constructing the sequence or by incrementally validating characters from both ends. Store its length if valid. Once the DP table is built, iterate through masks and enumerate submasks of the remaining characters to find the best partner subsequence. The DP state avoids recomputing palindrome checks repeatedly and keeps the solution efficient for strings up to length 12.
Bitmasking models subsequences naturally, while palindrome validation uses simple string checks. Problems involving subsequence enumeration and disjoint selection often combine bitmask techniques with backtracking ideas. Precomputing valid states is a classic pattern in dynamic programming over subsets.
Recommended for interviews: The bitmask approach with palindrome precomputation and submask enumeration is the expected solution. Interviewers want to see that you recognize the small constraint on n, model subsequences using bitmasks, and optimize pair checking using subset iteration. Starting with brute force shows understanding, but reaching the O(3^n) solution demonstrates strong problem‑solving skills.
Approach 1: Brute Force with Bitmasking
This approach utilizes bitmasking to enumerate all possible subsequences. Since the string length is constrained up to 12, we can afford to represent each subsequence with a bitmask. We will iterate over all combinations of two disjoint subsequences and check if each is palindromic before calculating the product of their lengths.
The solution enumerates all possible masks for subsequences using bit manipulation. It checks if a subsequence, represented by a mask, forms a palindrome using a helper function. If both generated subsequences are palindromes and disjoint, calculate their product of lengths, tracking the maximum found.
Complexity
Time Complexity: O(2^n * n^2). Space Complexity: O(1).
Approach 2: Dynamic Programming with State Representation
This approach leverages dynamic programming to keep track of previously calculated states. Due to small problem size, it offers a compromise between recalculation and precomputation, making it swifter than combinatorial methods.
This C solution employs dynamic programming to store palindromic subsequences and their lengths. It calculates the bitwise representation of subsequences, using a main loop to generate potential pair states.
Complexity
Time Complexity: O((3^n) * n), where n is the length of the string. Space Complexity: O(2^n).
Approach 3: Binary Enumeration
We notice that the length of the string s does not exceed 12, so we can use the method of binary enumeration to enumerate all subsequences of s. Suppose the length of s is n, we can use 2^n binary numbers of length n to represent all subsequences of s. For each binary number, the i-th bit being 1 means the i-th character of s is in the subsequence, and 0 means it is not in the subsequence. For each binary number, we judge whether it is a palindrome subsequence and record it in the array p.
Next, we enumerate each number i in p. If i is a palindrome subsequence, then we can enumerate a number j from the complement of i, mx = (2^n - 1) \oplus i. If j is also a palindrome subsequence, then i and j are the two palindrome subsequences we are looking for. Their lengths are the number of 1s in the binary representation of i and j, denoted as a and b, respectively. Then their product is a times b. We take the maximum of all possible a times b.
The time complexity is (2^n times n + 3^n), and the space complexity is O(2^n). Here, n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force with Bitmasking | Time Complexity: O(2^n * n^2). Space Complexity: O(1). |
| Dynamic Programming with State Representation | Time Complexity: O((3^n) * n), where n is the length of the string. Space Complexity: O(2^n). |
| Binary Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Bitmask Pair Check | O(n * 2^n + 4^n) | O(2^n) | Conceptual baseline to understand subsequence enumeration and disjoint mask checks |
| Bitmask with Submask Enumeration | O(n * 2^n + 3^n) | O(2^n) | Best practical solution when string length is small (n ≤ 12) |
| Dynamic Programming on Bitmask States | O(n * 2^n + 3^n) | O(2^n) | When you want to cache palindrome states and avoid repeated validation |
Video Solution
Maximum Product of the Length of Two Palindromic Subsequences - Leetcode 2002 - Python • NeetCode • 21,500 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Maximum Product of the Length of Two Palindromic Subsequences easy or hard?
Maximum Product of the Length of Two Palindromic Subsequences Python/Java solution
How to solve Maximum Product of the Length of Two Palindromic Subsequences in O(n)?
What is the best approach for Maximum Product of the Length of Two Palindromic Subsequences?
Is Maximum Product of the Length of Two Palindromic Subsequences asked at Google/Amazon/Meta?
What data structure is used in Maximum Product of the Length of Two Palindromic Subsequences?
What is the time complexity of Maximum Product of the Length of Two Palindromic Subsequences?
Ready to solve this problem?
Practice Maximum Product of the Length of Two Palindromic Subsequences with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor