NeetCode #118LC-2002MediumArrays & Hashing
← Back to All Problems#118 · #2002 · Maximum Product of the Length of Two Palindromic Subsequences(两个回文子序列长度的最大乘积)
📌 Problem Statement & Constraints
Given a string
s, find two disjoint palindromic subsequences of s and return the maximum product of their lengths. If no two disjoint palindromic subsequences exist, return 0. Constraints: 2 <= s.length <= 12, lowercase letters.💡 Core Algorithmic Approaches
- With
n <= 12, there are only2^n = 4096subsets, so bitmask enumeration is feasible. - Precompute which masks form a palindromic subsequence, along with their popcounts.
- For each palindromic mask, enumerate the submasks of its complement that are also palindromic and take the maximum product of the two sizes.
- Enumerating submasks of the complement costs
3^noverall, which is about 531k operations for n = 12 -- comfortably fast.
💻 Benchmark Python3 Implementation
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
size = {}
for mask in range(1, 1 << n):
sub = [s[i] for i in range(n) if mask >> i & 1]
if sub == sub[::-1]: # palindromic subsequence
size[mask] = len(sub)
res = 1
full = (1 << n) - 1
for mask in size:
comp = full ^ mask # candidate for the second subsequence
sub = comp
while sub:
if sub in size:
res = max(res, size[mask] * size[sub])
sub = (sub - 1) & comp # next submask of the complement
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(2^n * n + 3^n): O(2^n * n) to test all subsets for palindromicity and O(3^n) to enumerate disjoint pairs. With n <= 12 both are tiny.
💾 Space Complexity
O(2^n) for the palindromic-size map.
⚠️ Interview Pitfalls & Follow-ups
- Using
s[i:j]contiguous substrings instead of subsequences: the problem allows deleting characters, so any subset of positions qualifies. - Allowing the two subsequences to overlap: they must be disjoint, hence the complement-based submask enumeration.
- Trying a DP over intervals: workable but far more complex than the brute-force bitmask at n <= 12.
- Returning 0 when a valid pair exists: the initial value should be 1 so that the maximum is taken correctly, and any valid pair has a product of at least 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.