<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, s: str) -> int:

        def find_all_indexes(char: str, s: str) -> List[int]:
            answers = []
            startIndex = 0
            while True:
                try:
                    index = s.index(char, startIndex)
                except ValueError:
                    break
                answers.append(index)
                startIndex = index + 1
            return answers
        
        def truncate_at_last_index(char: str, s: str) -> str:
            indexes = find_all_indexes(char, s)
            last_index = indexes[-1]
            return s[:last_index]

        @cache
        def find_all_palindromes(s: str, largest_only=False) -> Set[str]:
            # print(f'FP({s})')
            if len(s) <= 1:
                return {s, ''}
            first = s[0]
            rest = s[1:]
            answerWithoutFirst = find_all_palindromes(rest, largest_only)
            if first in rest:
                center = truncate_at_last_index(first, rest)
                answerWithFirst = {
                    first + P + first
                    for P in find_all_palindromes(center, largest_only)
                }
            else:
                answerWithFirst = {first}
            all_answers = answerWithFirst | answerWithoutFirst
            if largest_only:
                # print(f'  Pruning {len(all_answers)} answers:')
                max_len = max([len(A) for A in all_answers])
                all_answers_List = [
                    A
                    for A in all_answers
                    if len(A) == max_len
                ]
                # print(f'    -> Found {len(all_answers)} of length {max_len}')
                all_answers = set(all_answers_List[:1])
                # print(f'    -> Trim to just {len(all_answers)}')
            return all_answers
        
        def remove_characters_in_order(chars: str, s: str) -> Set[str]:
            # print(f'RCIO({chars},{s}):')
            answers = set()
            queue = set()
            queue.add(
                ('', s)
            )
            for C in chars:
                # print(f'{C=}')
                newQ = set()
                for (answer, stringToCheck) in queue:
                    # print(f'->("{answer}","{stringToCheck}")')
                    indexes = find_all_indexes(C, stringToCheck)
                    if not indexes:
                        # print(f'  Char "{C}" not found in "{stringToCheck}"')
                        continue
                    for index in indexes:
                        # print(f'  Divide {stringToCheck} at {index=}:')
                        first = stringToCheck[:index]
                        restOfString = stringToCheck[index + 1:]
                        # print(f'    {first=} {restOfString=}')
                        newQ.add(
                            (answer + first, restOfString)
                        )
                        # print(f'      Q={(answer + first, restOfString)}')
                queue = newQ
            for (answer, stringToCheck) in queue:
                answers.add(answer + stringToCheck)
            return answers
        
        answers = []
        paindromes = find_all_palindromes(s, False)
        print(f'Found {len(paindromes)} palindromes:')
        for P in paindromes:
            L1 = len(P)
            print(f'  {L1=}: "{P}"')
            if L1 == 0:
                print(f'    (skip)')
                continue
            tOptions = remove_characters_in_order(P, s)
            print(f'    Found {len(tOptions)} complements:')
            for t in tOptions:
                print(f'    -> "{t}"')
                other_palindromes = find_all_palindromes(t, True)
                print(f'      Found {len(other_palindromes)} palindromes:')
                for Q in other_palindromes:
                    L2 = len(Q)
                    product = L1 * L2
                    print(f'        {L2=}: "{Q}"')
                    print(f'          {product=}')
                    answers.append(product)
        print(f'{answers=}')
        return max(answers)

18500