Maximum Product of the Length of Two Palindromic Subsequences - Video Solutions
Maximum Product of the Length of Two Palindromic Subsequences - Leetcode 2002 - Python
Maximum Product of the Length of Two Palindromic Subsequences - Video Solution
Watch 9 video solutions for Maximum Product of the Length of Two Palindromic Subsequences, a medium level problem involving String, Dynamic Programming, Backtracking. This walkthrough by NeetCode has 21,500 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |