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.

&nbsp;
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.


&nbsp;
Constraints:


	2 &lt;= s.length &lt;= 12
	s consists of lowercase English letters only.


class Solution:
    def maxProduct(self, s: str) -> int:
        # n <= 12, which means the search space is small
        n = len(s)
        arr = []
        
        for mask in range(1, 1<<n):
            subseq = ''
            for i in range(n):
                # convert the bitmask to the actual subsequence
                if mask & (1 << i) > 0:
                    subseq += s[i]
            if subseq == subseq[::-1]:
                arr.append((mask, len(subseq)))
        
        result = 1
        for (mask1, len1), (mask2, len2) in product(arr, arr):
            # disjoint
            if mask1 & mask2 == 0:
                result = max(result, len1 * len2)
        return result
class Solution {
    int res = 0;
    
    public int maxProduct(String s) {
        char[] strArr = s.toCharArray();
        dfs(strArr, 0, "", "");
        return res;
    }

    public void dfs(char[] strArr, int i, String s1, String s2){
        if(i >= strArr.length){
            if(isPalindromic(s1) && isPalindromic(s2))
                res = Math.max(res, s1.length()*s2.length());
            return;
        }
        dfs(strArr, i+1, s1 + strArr[i], s2);
        dfs(strArr, i+1, s1, s2 + strArr[i]);
        dfs(strArr, i+1, s1, s2);
    }

    public boolean isPalindromic(String str){
        int j = str.length() - 1;
        char[] strArr = str.toCharArray();
        for (int i = 0; i < j; i ++){
            if (strArr[i] != strArr[j])
                return false;
            j--;
        }
        return true;
    }
}
class Solution {
public:
    int lca(string &s)
    {
        int n=s.size();
        string s1=s;
        string s2=s;
        reverse(s2.begin(),s2.end());
        int dp[s.size()+1][s.size()+1];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=(s1[i-1]==s2[j-1])?1+dp[i-1][j-1]:max(dp[i][j-1],dp[i-1][j]);
            }
        }
        return dp[n][n];
    }
    int maxProduct(string s) 
    {
        int ans=0;
        int n=s.size();
        for(int i=1;i<(1<<n)-1;i++)
        {
            string s1="",s2="";
            for(int j=0;j<n;j++)
            {
                if(i&(1<<j))
                {
                    s1.push_back(s[j]);
                }
                else
                {
                    s2.push_back(s[j]);
                }
            }
            ans=max(ans,lca(s1)*lca(s2));
        }
        return ans;
    }
    
};
/**
 * @param {string} s
 * @return {number}
 */
var maxProduct = function(s) {
    const n = s.length;
    let map = new Map();
    let res = 0;

    for(let mask = 1; mask < 2 ** n;mask++){
        let str = "";
        for(let i = 0; i < n;i++){
            if(mask & (1 << i)){
                str += s.charAt(n - 1 - i);
            }
        }
        if(isPalindrom(str)){
            let length = str.length;
            map.set(mask,length);
        }
    }

    map.forEach((l1,m1) => {
        map.forEach((l2,m2) => {
            if((m1 & m2) == 0){
                res = Math.max(res,l1 * l2);
            }
        })
    })

    return res;
};

function isPalindrom(str){
    let l = 0;
    let r = str.length - 1;

    while(l < r){
        if(str.charAt(l) != str.charAt(r)){
            return false;
        }
        l++;
        r--;
    }

    return true;
}
Maximum Product of the Length of Two Palindromic Subsequences