[Python] Clean & Simple, bitmask
python\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        # n <= 12, which means the search space is small\n        n = len(s)\n        arr = [
```python\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        # n <= 12, which means the search space is small\n        n = len(s)\n        arr = []\n        \n        for mask in range(1, 1<<n):\n            subseq = \'\'\n            for i in range(n):\n                # convert the bitmask to the actual subsequence\n                if mask & (1 << i) > 0:\n                    subseq += s[i]\n            if subseq == subseq[::-1]:\n                arr.append((mask, len(subseq)))\n        \n        result = 1\n        for (mask1, len1), (mask2, len2) in product(arr, arr):\n            # disjoint\n            if mask1 & mask2 == 0:\n                result = max(result, len1 * len2)\n        return result\n```\n\nA slightly improved version, to break early when checking the results\n\n```python\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        # n <= 12, which means the search space is small\n        n = len(s)\n        arr = []\n        \n        for mask in range(1, 1<<n):\n            subseq = \'\'\n            for i in range(n):\n                # convert the bitmask to the actual subsequence\n                if mask & (1 << i) > 0:\n                    subseq += s[i]\n            if subseq == subseq[::-1]:\n                arr.append((mask, len(subseq)))\n        \n        arr.sort(key=lambda x: x[1], reverse=True)\n        result = 1\n        for i in range(len(arr)):\n            mask1, len1 = arr[i]\n            # break early\n            if len1 ** 2 < result: break\n            for j in range(i+1, len(arr)):\n                mask2, len2 = arr[j]\n                # disjoint\n                if mask1 & mask2 == 0 and len1 * len2 > result:\n                    result = len1 * len2\n                    break\n        \n        return result\n```
['Python']