Maximum Product of the Length of Two Palindromic Subsequences

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:

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.

SOLUTION:

class Solution:
    def maxPalindrome(self, s, i, j, cache):
        key = 1100 * i + j
        if key in cache:
            return cache[key]
        if i == j:
            cache[key] = 1
        elif s[i] == s[j] and i + 1 == j:
            cache[key] = 2
        elif s[i] == s[j]:
            cache[key] = self.maxPalindrome(s, i + 1, j - 1, cache) + 2
        else:
            cache[key] = max(self.maxPalindrome(s, i, j - 1, cache), self.maxPalindrome(s, i + 1, j, cache))
        return cache[key]

    def maxProduct(self, s: str) -> int:
        self.cache = {}
        maxP = float('-inf')
        n = len(s)
        for mask in range(1 << n):
            sub = ""
            rest = ""
            for j in range(n):
                if mask & (1 << j):
                    sub += s[j]
                else:
                    rest += s[j]
            if len(sub) > 0 and len(rest) > 0:
                maxP = max(maxP, self.maxPalindrome(sub, 0, len(sub) - 1, {}) * self.maxPalindrome(rest, 0, len(rest) - 1, {}))
        return maxP