Maximum Product of the Length of Two Palindromic Subsequences LeetCode solution in Python

1
class Solution:
2
    def maxProduct(self, s: str) -> int:
3
        # n <= 12, which means the search space is small
4
        n = len(s)
5
        arr = []
6

7
        for mask in range(1, 1 << n):
8
            subseq = ""
9
            for i in range(n):
10
                # convert the bitmask to the actual subsequence
11
                if mask & (1 << i) > 0:
12
                    subseq += s[i]
13
            if subseq == subseq[::-1]:
14
                arr.append((mask, len(subseq)))
15

16
        result = 1
17
        for (mask1, len1), (mask2, len2) in product(arr, arr):
18
            # disjoint
19
            if mask1 & mask2 == 0:
20
                result = max(result, len1 * len2)
21
        return result