# Maximum Product of the Length of Two Palindromic Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-the-length-of-two-palindromic-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** String
---
## 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.

**Example 1:**

![example-1](https://assets.glich.co/dsa/maximum-product-of-the-length-of-two-palindromic-subsequences/image0.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.

**Example 2:**

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

**Example 3:**

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

# Approaches
## Brute-Force with Bitmasking and Pairwise Check
This approach involves generating all possible subsequences of the input string `s`, checking which ones are palindromic, and then finding the best pair of disjoint palindromic subsequences by checking all pairs.
**Time:** O(n * 2^n + P^2), where P is the number of palindromic subsequences. In the worst case, P can be close to 2^n, making the complexity O(n * 2^n + 4^n). For n=12, this is computationally expensive. · **Space:** O(P), where P is the number of palindromic subsequences. In the worst case, this can be O(2^n) to store the masks and lengths.
**Pros:** Conceptually straightforward extension of generating all subsequences.
**Cons:** The pairwise check can be very slow if there are many palindromic subsequences, leading to a high time complexity that might not pass for larger constraints.
### Explanation
1.  **Generate all subsequences:** We can represent each subsequence using a bitmask of length `n` (where `n` is the length of `s`). A '1' at the `i`-th position in the mask means the character `s.charAt(i)` is included in the subsequence. We iterate through all `2^n` possible masks.
2.  **Identify palindromic subsequences:** For each mask, we construct the corresponding subsequence string. We then check if this string is a palindrome.
3.  **Store palindromes:** We store the masks of all palindromic subsequences and their lengths, for example, in a hash map where the key is the mask and the value is the length.
4.  **Find the best pair:** After identifying all palindromic subsequences, we iterate through all possible pairs of them. For each pair, we check if their corresponding masks are disjoint (i.e., their bitwise AND is zero). If they are disjoint, we calculate the product of their lengths and update our maximum product found so far.

```java
class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        Map<Integer, Integer> palindromeLengths = new HashMap<>();

        for (int mask = 1; mask < (1 << n); mask++) {
            StringBuilder sub = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sub.append(s.charAt(i));
                }
            }
            if (isPalindrome(sub.toString())) {
                palindromeLengths.put(mask, sub.length());
            }
        }

        int maxProd = 0;
        List<Integer> masks = new ArrayList<>(palindromeLengths.keySet());
        for (int i = 0; i < masks.size(); i++) {
            for (int j = i; j < masks.size(); j++) {
                int mask1 = masks.get(i);
                int mask2 = masks.get(j);
                if ((mask1 & mask2) == 0) {
                    int product = palindromeLengths.get(mask1) * palindromeLengths.get(mask2);
                    maxProd = Math.max(maxProd, product);
                }
            }
        }
        return maxProd;
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize `n = s.length()`.
- Create a map `palindromes` to store `(mask, length)` for palindromic subsequences.
- Iterate `mask` from `1` to `(1 << n) - 1`:
    - Construct the subsequence `sub` from `s` using `mask`.
    - If `sub` is a palindrome, put `(mask, sub.length())` into `palindromes`.
- Initialize `maxProduct = 0`.
- Convert the keys of `palindromes` into a list `pMasks`.
- Iterate through all pairs `(mask1, mask2)` from `pMasks`:
    - If `(mask1 & mask2) == 0` (the subsequences are disjoint):
        - `product = palindromes.get(mask1) * palindromes.get(mask2)`.
        - `maxProduct = max(maxProduct, product)`.
- Return `maxProduct`.

## Backtracking with 3-way Partitioning
This approach uses recursion (backtracking) to explore all possible ways to partition the characters of the string `s` into three groups: one for the first subsequence, one for the second, and one for unused characters.
**Time:** O(n * 3^n). There are `3^n` possible partitions. For each partition, we perform two palindrome checks, which take `O(n)` time in total. · **Space:** O(n). The recursion depth is `n`, and the `StringBuilder`s also take `O(n)` space.
**Pros:** Relatively simple to implement and understand.; It directly maps to the problem's combinatorial nature.
**Cons:** Can be slow for larger `n`, though it's acceptable for `n <= 12`.
### Explanation
We define a recursive function, say `backtrack(index, s1, s2)`, that tries to build two disjoint subsequences, `s1` and `s2`. The `index` parameter tracks the current character in `s` being considered.
For each character `s.charAt(index)`, we have three choices:
1.  Append it to `s1`.
2.  Append it to `s2`.
3.  Ignore it (don't add to either `s1` or `s2`).
The recursion proceeds by making one of these three choices and then calling itself for the next index, `index + 1`.
The base case for the recursion is when `index` reaches the end of the string `s`. At this point, we have formed two complete (though possibly empty) subsequences, `s1` and `s2`. We check if both are palindromes. If they are, we calculate the product of their lengths and update a global maximum.

```java
class Solution {
    int maxProd = 0;

    public int maxProduct(String s) {
        backtrack(0, s, new StringBuilder(), new StringBuilder());
        return maxProd;
    }

    private void backtrack(int index, String s, StringBuilder s1, StringBuilder s2) {
        if (index == s.length()) {
            if (isPalindrome(s1) && isPalindrome(s2)) {
                maxProd = Math.max(maxProd, s1.length() * s2.length());
            }
            return;
        }

        char c = s.charAt(index);

        // Choice 1: Add to s1
        s1.append(c);
        backtrack(index + 1, s, s1, s2);
        s1.deleteCharAt(s1.length() - 1); // backtrack

        // Choice 2: Add to s2
        s2.append(c);
        backtrack(index + 1, s, s1, s2);
        s2.deleteCharAt(s2.length() - 1); // backtrack

        // Choice 3: Ignore
        backtrack(index + 1, s, s1, s2);
    }

    private boolean isPalindrome(StringBuilder sb) {
        if (sb.length() == 0) return true;
        int left = 0, right = sb.length() - 1;
        while (left < right) {
            if (sb.charAt(left) != sb.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize a global variable `maxProduct = 0`.
- Define a recursive function `backtrack(index, s1, s2)`:
    - **Base Case:** If `index == s.length()`:
        - If `s1` is a palindrome and `s2` is a palindrome:
            - `maxProduct = max(maxProduct, s1.length() * s2.length())`.
        - Return.
    - **Recursive Step:**
        - **Choice 1 (add to s1):** `backtrack(index + 1, s1 + s.charAt(index), s2)`.
        - **Choice 2 (add to s2):** `backtrack(index + 1, s1, s2 + s.charAt(index))`.
        - **Choice 3 (ignore):** `backtrack(index + 1, s1, s2)`.
- Start the process by calling `backtrack(0, "", "")`.
- Return `maxProduct`.
- Using `StringBuilder` instead of string concatenation is recommended for better performance.

## Bitmasking with Dynamic Programming on Subsets
This is the most efficient approach. It leverages bitmasking to represent subsequences and dynamic programming to avoid redundant computations. The core idea is to first precompute the lengths of all palindromic subsequences and then efficiently find the best pair.
**Time:** O(n * 2^n). Precomputing palindrome lengths takes O(n * 2^n). The DP on subsets step takes O(n * 2^n). The final loop takes O(2^n). The total is dominated by O(n * 2^n). · **Space:** O(2^n) for the `dp` array.
**Pros:** Highly efficient and guaranteed to pass within time limits for the given constraints.
**Cons:** More complex to understand and implement, requiring knowledge of bitmasking and dynamic programming on subsets.
### Explanation
The approach consists of three main steps:
1.  **Precompute Palindrome Lengths:** We iterate through all `2^n` masks. For each mask, we generate the corresponding subsequence and check if it's a palindrome. We store the length of the subsequence if it is a palindrome, and 0 otherwise, in an array `dp` of size `2^n`. `dp[mask]` will hold the length.
2.  **DP on Subsets:** We want to find, for each mask, the length of the longest palindromic subsequence that is a *submask* of it. We can compute this using a DP technique. Let `dp[mask]` be the length of the longest palindromic subsequence that can be formed using a subset of characters represented by `mask`. We can compute this `dp` array as follows:
    -   Initialize `dp[mask]` with the length if the subsequence for `mask` is a palindrome, 0 otherwise.
    -   Then, for each bit `i` from `0` to `n-1`, we iterate through all masks. If the `i`-th bit is set in a `mask`, it means the character `s.charAt(i)` is included. The longest palindrome for this `mask` is either one that includes `s.charAt(i)` or one that doesn't. The latter is `dp[mask ^ (1 << i)]`. So, we update `dp[mask] = max(dp[mask], dp[mask ^ (1 << i)])`. This propagates the maximum lengths from submasks to their supermasks.
3.  **Find Maximum Product:** After computing the `dp` array, `dp[mask]` contains the length of the longest palindromic subsequence for any submask of `mask`. We can now iterate through all possible masks `mask1` from `1` to `(1 << n) - 1`. For each `mask1`, we consider it for the first subsequence. The remaining characters are represented by the complement mask, `mask2 = ((1 << n) - 1) ^ mask1`. The length of the longest palindromic subsequence from `mask1` is `dp[mask1]`, and from `mask2` is `dp[mask2]`. We calculate their product and update the overall maximum.

```java
class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        int N = 1 << n;
        int[] dp = new int[N];

        for (int mask = 1; mask < N; mask++) {
            StringBuilder sub = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sub.append(s.charAt(i));
                }
            }
            if (isPalindrome(sub.toString())) {
                dp[mask] = sub.length();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int mask = 1; mask < N; mask++) {
                if ((mask & (1 << i)) != 0) {
                    dp[mask] = Math.max(dp[mask], dp[mask ^ (1 << i)]);
                }
            }
        }

        int maxProd = 0;
        for (int mask1 = 1; mask1 < N; mask1++) {
            int mask2 = (N - 1) ^ mask1;
            maxProd = Math.max(maxProd, dp[mask1] * dp[mask2]);
        }

        return maxProd;
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize `n = s.length()`.
- Create an array `dp` of size `(1 << n)`.
- Iterate `mask` from `1` to `(1 << n) - 1`:
    - Construct subsequence `sub` from `s` using `mask`.
    - If `sub` is a palindrome, set `dp[mask] = sub.length()`.
- For `i` from `0` to `n-1`:
    - For `mask` from `1` to `(1 << n) - 1`:
        - If the `i`-th bit of `mask` is set (`(mask >> i) & 1 == 1`):
            - `dp[mask] = max(dp[mask], dp[mask ^ (1 << i)])`.
- Initialize `maxProduct = 0`.
- Iterate `mask1` from `1` to `(1 << n) - 1`:
    - `mask2 = ((1 << n) - 1) ^ mask1`.
    - `product = dp[mask1] * dp[mask2]`.
    - `maxProduct = max(maxProduct, product)`.
- Return `maxProduct`.

# Solutions
### Java

```java
class Solution {
public
  int maxProduct(String s) {
    int n = s.length();
    boolean[] p = new boolean[1 << n];
    Arrays.fill(p, true);
    for (int k = 1; k < 1 << n; ++k) {
      for (int i = 0, j = n - 1; i < n; ++i, --j) {
        while (i < j && (k >> i & 1) == 0) {
          ++i;
        }
        while (i < j && (k >> j & 1) == 0) {
          --j;
        }
        if (i < j && s.charAt(i) != s.charAt(j)) {
          p[k] = false;
          break;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i < 1 << n; ++i) {
      if (p[i]) {
        int a = Integer.bitCount(i);
        int mx = ((1 << n) - 1) ^ i;
        for (int j = mx; j > 0; j = (j - 1) & mx) {
          if (p[j]) {
            int b = Integer.bitCount(j);
            ans = Math.max(ans, a * b);
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProduct(string s) {
    int n = s.size();
    vector<bool> p(1 << n, true);
    for (int k = 1; k < 1 << n; ++k) {
      for (int i = 0, j = n - 1; i < j; ++i, --j) {
        while (i < j && !(k >> i & 1)) {
          ++i;
        }
        while (i < j && !(k >> j & 1)) {
          --j;
        }
        if (i < j && s[i] != s[j]) {
          p[k] = false;
          break;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i < 1 << n; ++i) {
      if (p[i]) {
        int a = __builtin_popcount(i);
        int mx = ((1 << n) - 1) ^ i;
        for (int j = mx; j; j = (j - 1) & mx) {
          if (p[j]) {
            int b = __builtin_popcount(j);
            ans = max(ans, a * b);
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

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

```