⚡Flashcard Drill➔
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

  1. With n <= 12, there are only 2^n = 4096 subsets, so bitmask enumeration is feasible.
  2. Precompute which masks form a palindromic subsequence, along with their popcounts.
  3. For each palindromic mask, enumerate the submasks of its complement that are also palindromic and take the maximum product of the two sizes.
  4. Enumerating submasks of the complement costs 3^n overall, 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems