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 <= 12s consists of lowercase English letters only.In #2002 Maximum Product of the Length of Two Palindromic Subsequences, the goal is to choose two disjoint subsequences from a string such that both are palindromes and the product of their lengths is maximized. Since the string length is small, a common strategy is to represent subsequences using a bitmask. Each mask indicates which characters are selected.
For every mask, build the subsequence and check if it forms a palindrome. If it does, store its length. Then compare pairs of masks that have (mask1 & mask2) == 0, ensuring the subsequences do not share characters. Track the maximum product of their lengths.
This approach leverages bit manipulation to efficiently enumerate subsequences and avoids redundant checks. Some optimizations include precomputing palindromic masks or pruning shorter candidates early. The overall complexity is manageable because the constraint on the string length keeps 2^n manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Enumeration of Subsequences | O(n * 2^n + 2^n * 2^n) | O(2^n) |
| Optimized Bitmask with Palindrome Precheck | O(n * 2^n) | O(2^n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Could you generate all possible pairs of disjoint subsequences?
Could you find the maximum length palindrome in each subsequence for a pair of disjoint subsequences?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bitmasking allows you to represent each subsequence as a binary number where each bit indicates whether a character is included. This makes it easy to generate all subsequences and quickly check whether two subsequences share characters using bitwise AND operations.
Problems involving palindromes, subsequences, and bitmask enumeration are common in FAANG-style interviews. While the exact question may vary, the techniques of bit manipulation, dynamic programming, and combinational search are frequently tested.
Bitmasks are the most useful representation because they efficiently encode subsequences and allow quick checks for overlap using bit operations. Arrays or hash maps can store the length of palindromic subsequences corresponding to each mask.
A common optimal approach uses bitmasking to enumerate all subsequences and check which ones are palindromes. The lengths of valid palindromic subsequences are stored, and pairs of disjoint masks are compared to maximize the product. This works efficiently because the string length is relatively small.