> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximum Product of the Length of Two

> Tested Python solution for LeetCode 2002 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 2002, [Medium](/catalog/medium). Topics: [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2002   # by problem number
lcpy gen -s maximum_product_of_the_length_of_two_palindromic_subsequences   # by problem name
```

## Problem

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.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-subsequences.png)

```
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.
```

```
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.
```

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_product_of_the_length_of_two_palindromic_subsequences/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_product_of_the_length_of_two_palindromic_subsequences/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(2^n * n + 3^n) with n = len(s)
    # Space: O(2^n)
    def max_product(self, s: str) -> int:
        n = len(s)

        def is_palindrome(mask: int) -> bool:
            chars = [s[i] for i in range(n) if mask >> i & 1]
            return chars == chars[::-1]

        length = [0] * (1 << n)
        palindromes: list[int] = []
        for mask in range(1, 1 << n):
            if is_palindrome(mask):
                length[mask] = mask.bit_count()
                palindromes.append(mask)

        best = 0
        for a in palindromes:
            if length[a] * length[a] <= best:
                continue
            remaining = ((1 << n) - 1) ^ a
            # enumerate all submasks of the complement of a
            sub = remaining
            while sub:
                if length[sub]:
                    best = max(best, length[a] * length[sub])
                sub = (sub - 1) & remaining
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(2^n \* n + 3^n) with n = len(s) | O(2^n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.