<p>Given a string <code>s</code>, find two <strong>disjoint palindromic subsequences</strong> of <code>s</code> such that the <strong>product</strong> of their lengths is <strong>maximized</strong>. The two subsequences are <strong>disjoint</strong> if they do not both pick a character at the same index.</p>

<p>Return <em>the <strong>maximum</strong> possible <strong>product</strong> of the lengths of the two palindromic subsequences</em>.</p>

<p>A <strong>subsequence</strong> 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 <strong>palindromic</strong> if it reads the same forward and backward.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="example-1" src="https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-subsequences.png" style="width: 550px; height: 124px;" />
<pre>
<strong>Input:</strong> s = &quot;leetcodecom&quot;
<strong>Output:</strong> 9
<strong>Explanation</strong>: An optimal solution is to choose &quot;ete&quot; for the 1<sup>st</sup> subsequence and &quot;cdc&quot; for the 2<sup>nd</sup> subsequence.
The product of their lengths is: 3 * 3 = 9.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bb&quot;
<strong>Output:</strong> 1
<strong>Explanation</strong>: An optimal solution is to choose &quot;b&quot; (the first character) for the 1<sup>st</sup> subsequence and &quot;b&quot; (the second character) for the 2<sup>nd</sup> subsequence.
The product of their lengths is: 1 * 1 = 1.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;accbcaxxcxx&quot;
<strong>Output:</strong> 25
<strong>Explanation</strong>: An optimal solution is to choose &quot;accca&quot; for the 1<sup>st</sup> subsequence and &quot;xxcxx&quot; for the 2<sup>nd</sup> subsequence.
The product of their lengths is: 5 * 5 = 25.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 12</code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

class Solution:
    def maxProduct(self, string: str) -> int:
        """
        [Intuition]
        use bit mask to generate all combinations
        convert that into actual sequence
        
        find product of of a pair in all the possible sequence palindromes
        make sure their bit mask & to 0
        then update max res
        
        """
        n = len(string)
        max_res = 1
        
        # create a list to hold all palindromes
        p_lst = []
        # create all mask combination to digit length of n
        for mask in range(1, 1<<n):
            #convert string into actual sequence
            seq = ''
            for i in range(n):
                if mask & (1<<i)>0:
                    seq += string[i]
                # check palindrome
            if seq == seq[::-1]:
                p_lst.append((mask, len(seq)))
                    
        # create all possible product
        for (mask1, len1), (mask2, len2) in product(p_lst, p_lst):
            # check disjoint
            if mask1 & mask2 == 0:
                max_res = max(max_res, len1*len2)
        
        return max_res
    
    # my solution. Does not work
#     max_res = 0
#     def maxProduct(self, string: str) -> int:
#         """
#         [Enumerate]
#         if s = 'speedplanes', a = 'peep', b = 'ses', then res = 12
        
#         if s = 'abaabacabfaa', possible a = 'abaaba', b = 'aaa', res = 18, 
#                             another possible a = 'baab', b = 'aabaa', then res = 20
#                             another possible a = 'baabaab', b = 'aaa', then res = 21
        
#         if s = 'aaaaaa', a = 'aaa', b = 'aaa', then res = 9
        
#         [Intuition]
#         we use two pointers to traverse the string
#         we start a palindrome with each left letter, then we try to find the one on the right
#         when we find a solution, we remove them from the string, then run the string again for the sec sequence
#         we then calcualte the product
#         we can keep a max_res to the max product
#         we can use dfs to structure our code
        
#         [Implementation/Brute Force]

                    
#         """
        
#         # if size of the string is two, return 1
#         if len(string) == 2: return 1
                
#         # loop from the left of the string
#         for i in range(len(string)):
#             # revoke finding_A(on rest of the string)
#             self.find_A(string[i:])
#         return self.max_res

        
#     def find_A(self, string):
#         # create a running A = ''
#         A = ''
#         # make two pointers
#         i, j = 0, len(string)-1
#         # for each of the i
#         while i<j:
#             l = string[i]
#             # for each one we start second pointer from the right, moving to the left
#             try:
#                 while i<j and string[j] != l:
#                     j-=1
#             except:
#                 print('string', string)
#                 print('jjjjjjjjjjjjjjj', j)
#             # if we find a match,
#             if i<j:
#                 # we move those two letters to A
#                 mid = len(A)//2
#                 A = A[:mid]+l+l+A[mid:]
#                 string = string[:i]+string[i+1:]
#                 string = string[:j-1]+string[j:]
#                 j-=1
#                 # start the function finding_B on the rest of the string, passing in length of A
#                 if i<j-1:
#                     for k in range(i+1,j):
#                         new_string = string[:k]+string[k+1:]
#                         print(A)
#                         print(new_string)
#                         print(self.max_res)
#                         self.find_B(new_string, len(A)+1)
#                 else:
#                     self.find_B(string, len(A))

#             i+=1
        
#     def find_B(self, string, len_A):
#         # create a running B = ''
#         print(len_A)
#         B = ''
#         i, j = 0, len(string)-1
#         # loop through all the element
#         while i<j:
#             l = string[i]
#             # for each one we start second pointer from the right, moving to the left
#             while i<j and l != string[j]:
#                 j-=1
#             # if we find a match
#             if i<j:
#                 # we move those two letters to B
#                 mid = len(B)//2
#                 B = B[:mid]+l+l+B[mid:]
#                 # calcualte the product
#                 len_B = len(B)
#                 print('B', B)
#                 if i<j-1:
#                     len_B +=1
#                 print(len_B)
#                 prod = len_A * len_B
#                 # reset max_product
#                 self.max_res = max(self.max_res, prod)
#                 j-=1
#             i+=1
1743