LeetCode 2002 - Maximum Product of the Length of Two Palindromic Subsequences
The problem is asking us to find two disjoint palindromic subsequences from a given string s such that the product of their lengths is maximized. A subsequence is derived by deleting zero or more characters from the original string while keeping the relative order intact.
Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask
Solution
Problem Understanding
The problem is asking us to find two disjoint palindromic subsequences from a given string s such that the product of their lengths is maximized. A subsequence is derived by deleting zero or more characters from the original string while keeping the relative order intact. A palindrome reads the same forward and backward, such as "aba" or "cdc". Two subsequences are disjoint if they do not share any character at the same index in the original string.
The input is a string s of length between 2 and 12 consisting of lowercase letters. The small maximum length indicates that a solution can consider all possible subsequences, since the total number of subsequences is 2^n and 2^12 = 4096, which is computationally feasible.
The expected output is a single integer representing the maximum product of the lengths of any two disjoint palindromic subsequences. Edge cases include very short strings (length 2), strings where all characters are identical, or strings where the optimal palindromes use non-contiguous letters.
Approaches
The brute-force approach is to generate all possible subsequences of s. For each subsequence, check if it is a palindrome and store its bitmask representation and length. Then, iterate over all pairs of palindromic subsequences and check if they are disjoint using the bitmasks. If they are, compute the product of their lengths and keep track of the maximum. This approach is correct because it exhaustively considers every possible subsequence combination, but it is slow because there are 2^n subsequences and up to (2^n)^2 pairs to check.
The key observation to optimize this is that each subsequence can be represented as a bitmask where a set bit indicates the inclusion of the corresponding character. Checking disjointness between two subsequences reduces to a bitwise AND operation. By iterating over all bitmasks once and storing only palindromes, we avoid redundant checks and achieve better performance while still being feasible for the given constraints.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n * n + 2^(2n)) | O(2^n) | Generate all subsequences, check palindrome, check all pairs |
| Optimal | O(2^n * n + 2^(2n)) | O(2^n) | Use bitmask representation and store palindromes to efficiently check disjoint subsequences |
Algorithm Walkthrough
- Initialize an empty dictionary
palindrome_masksto store valid palindromic subsequences as{bitmask: length}. - Iterate over all integers from
1to2^n - 1representing all possible non-empty subsequences using their bitmask. Each bit in the mask represents whether the corresponding character insis included. - For each mask, construct the corresponding subsequence by including characters where the mask bit is set. Check if the subsequence is a palindrome.
- If the subsequence is a palindrome, store it in
palindrome_maskswith its length. - Iterate over all pairs of palindromic masks. For each pair, check if the two masks are disjoint using a bitwise AND (
mask1 & mask2 == 0). - If disjoint, compute the product of their lengths. Keep track of the maximum product seen.
- Return the maximum product.
Why it works: Each subsequence is uniquely represented by its bitmask, so we can efficiently check for disjointness without repeatedly reconstructing subsequences. By iterating through all subsequences and checking palindromes, we ensure that all valid combinations are considered. The bitmask guarantees no overlap in characters when AND is zero.
Python Solution
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
palindrome_masks = {}
def is_palindrome(subseq: str) -> bool:
return subseq == subseq[::-1]
for mask in range(1, 1 << n):
subseq = ''.join(s[i] for i in range(n) if (mask >> i) & 1)
if is_palindrome(subseq):
palindrome_masks[mask] = len(subseq)
max_product = 0
masks = list(palindrome_masks.keys())
for i in range(len(masks)):
for j in range(i + 1, len(masks)):
if masks[i] & masks[j] == 0:
product = palindrome_masks[masks[i]] * palindrome_masks[masks[j]]
max_product = max(max_product, product)
return max_product
The implementation first computes all palindromic subsequences using bitmasking. The helper is_palindrome checks each candidate. Storing masks avoids generating overlapping pairs unnecessarily. The double loop over masks efficiently computes the maximum product for disjoint subsequences.
Go Solution
func maxProduct(s string) int {
n := len(s)
palindromeMasks := make(map[int]int)
isPalindrome := func(subseq string) bool {
left, right := 0, len(subseq)-1
for left < right {
if subseq[left] != subseq[right] {
return false
}
left++
right--
}
return true
}
for mask := 1; mask < (1 << n); mask++ {
subseq := ""
for i := 0; i < n; i++ {
if (mask>>i)&1 == 1 {
subseq += string(s[i])
}
}
if isPalindrome(subseq) {
palindromeMasks[mask] = len(subseq)
}
}
maxProduct := 0
masks := make([]int, 0, len(palindromeMasks))
for m := range palindromeMasks {
masks = append(masks, m)
}
for i := 0; i < len(masks); i++ {
for j := i + 1; j < len(masks); j++ {
if masks[i]&masks[j] == 0 {
product := palindromeMasks[masks[i]] * palindromeMasks[masks[j]]
if product > maxProduct {
maxProduct = product
}
}
}
}
return maxProduct
}
The Go implementation mirrors the Python logic. Strings are concatenated using += for each selected character. The palindrome check is explicit with a two-pointer method. Maps and slices are used to store masks and iterate through combinations.
Worked Examples
Example 1: s = "leetcodecom"
- All subsequences are generated via bitmask. Palindromic subsequences include "l", "e", "t", "ee", "ete", "cdc", etc.
- Optimal combination: mask representing "ete" and mask representing "cdc" are disjoint.
- Product:
3 * 3 = 9.
Example 2: s = "bb"
- Subsequence masks: "b" (first), "b" (second), "bb".
- Disjoint pairs: first "b" and second "b".
- Product:
1 * 1 = 1.
Example 3: s = "accbcaxxcxx"
- Palindromes include "accca", "xxcxx".
- Masks are disjoint, product:
5 * 5 = 25.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(2^n * n + 2^(2n)) | Generate all subsequences with O(n) per mask, check all pairs for disjointness |
| Space | O(2^n) | Store bitmask and length of all palindromic subsequences |
The small constraint n <= 12 ensures this solution is practical.
Test Cases
# Provided examples
assert Solution().maxProduct("leetcodecom") == 9 # Example 1
assert Solution().maxProduct("bb") == 1 # Example 2
assert Solution().maxProduct("accbcaxxcxx") == 25 # Example 3
# Edge and additional cases
assert Solution().maxProduct("ab") == 1 # minimal length, both chars different
assert Solution().maxProduct("aa") == 1 # minimal length, identical characters
assert Solution().maxProduct("abcd") == 1 # no long palindromes, only single chars
assert Solution().maxProduct("racecar") == 9 # full string palindrome and sub-palindromes
assert Solution().maxProduct("aaaaa") == 9 # all identical characters
| Test | Why |
|---|---|
| "leetcodecom" | Example with overlapping optimal palindromes |
| "bb" | Short string, identical characters |
| "accbcaxxcxx" | Longer string with optimal palindromes in different positions |
| "ab" | Minimal length, no repeated characters |
| "aa" | Minimal length, identical characters |
| "abcd" | No palindromes longer than 1 |
| "racecar" | Palindrome using full string |
| "aaaaa" | All identical characters, multiple ways to pick palindromes |
Edge Cases
- Minimal Length Strings: Strings of length 2 like "ab" or "aa" could be mishandled if indexing assumes longer strings. The implementation correctly handles them by iterating over all masks starting from 1.
- **All