#2002

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Product of the Length of Two Palindromic Subsequences

Find two disjoint palindromic subsequences in a string to maximize the product of their lengths efficiently using dynamic programming.

string dynamic programming backtracking bit manipulation bitmask

Problem Statement

Given a string s, determine two non-overlapping subsequences that are both palindromic, such that their length product is as large as possible. Characters cannot be shared between the two subsequences.

Return the highest achievable product of the lengths of these two palindromic subsequences. A subsequence keeps character order from s, and a palindrome reads the same forward and backward.

Examples

Example 1

Input: s = "leetcodecom"

Output: 9

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

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

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 <= 12
s consists of lowercase English letters only.

Solution Approach

Generate all subsequences using bitmasking

Use bitmasks to represent every possible subsequence of s. Each bit indicates whether a character is included, allowing efficient enumeration of all combinations while preserving original order.

Check palindromic subsequences and disjointness

For each pair of subsequences, verify they are palindromic and have no overlapping indices. Use bitwise AND to quickly detect shared characters between two bitmasks.

Maximize product using dynamic programming

Store lengths of palindromic subsequences for each mask. Iterate over all mask pairs to compute the product of their lengths, updating a running maximum to find the final result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(2^n * 2^n * n) in the worst case due to enumerating all subsequence pairs and checking palindromes of length n. Space complexity is O(2^n * n) to store palindrome lengths for each subsequence mask.

What Interviewers Usually Probe

Can you generate all subsequences and efficiently check for palindromes?
Consider bitmasking to represent subsequences and check disjoint characters quickly.
Can you optimize by storing palindromic lengths to avoid repeated computation?

Common Pitfalls or Variants

Common pitfalls

Failing to ensure the two subsequences are disjoint by index.
Rechecking palindrome property repeatedly instead of caching results.
Overlooking subsequences that maximize product due to greedy selection of longest palindromes first.

Follow-up variants

Find the maximum sum of lengths instead of product for two disjoint palindromic subsequences.
Allow three disjoint palindromic subsequences and maximize the product of their lengths.
Restrict subsequences to a specific minimum length and compute the maximum product.

FAQ

What is the main pattern used in Maximum Product of the Length of Two Palindromic Subsequences?

The problem primarily uses state transition dynamic programming combined with bitmasking to handle all subsequence combinations efficiently.

Can this problem be solved with simple recursion?

Recursion alone is too slow due to exponential subsequence pairs; bitmasking with DP is needed for acceptable performance.

Why is bitmasking useful here?

Bitmasking allows efficient representation of subsequences and quick checks for disjoint characters using bitwise operations.

What is the maximum input size to consider?

The string length is constrained between 2 and 12 characters, so enumerating all subsequences is feasible.

How do you check if a subsequence is a palindrome efficiently?

Store previously computed palindromic lengths or use a two-pointer check on the subsequence represented by a bitmask.

terminal

Solution

Solution 1: Binary Enumeration

We notice that the length of the string $s$ does not exceed $12$, so we can use the method of binary enumeration to enumerate all subsequences of $s$. Suppose the length of $s$ is $n$, we can use $2^n$ binary numbers of length $n$ to represent all subsequences of $s$. For each binary number, the $i$-th bit being $1$ means the $i$-th character of $s$ is in the subsequence, and $0$ means it is not in the subsequence. For each binary number, we judge whether it is a palindrome subsequence and record it in the array $p$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        p = [True] * (1 << n)
        for k in range(1, 1 << n):
            i, j = 0, n - 1
            while i < j:
                while i < j and (k >> i & 1) == 0:
                    i += 1
                while i < j and (k >> j & 1) == 0:
                    j -= 1
                if i < j and s[i] != s[j]:
                    p[k] = False
                    break
                i, j = i + 1, j - 1
        ans = 0
        for i in range(1, 1 << n):
            if p[i]:
                mx = ((1 << n) - 1) ^ i
                j = mx
                a = i.bit_count()
                while j:
                    if p[j]:
                        b = j.bit_count()
                        ans = max(ans, a * b)
                    j = (j - 1) & mx
        return ans

Continue Practicing

#1255 maximum score words formed by letters #1986 minimum number of work sessions to finish the tasks #1947 maximum compatibility score sum