Explained approach with time and space complexities. 🔥
Intuition \n Describe your first thoughts on how to solve this problem. \nUtilize bitmasking to efficiently generate all possible subsequences of the string and
# Intuition \n<!-- Describe your first thoughts on how to solve this problem. -->\nUtilize bitmasking to efficiently generate all possible subsequences of the string and to verify if two strings are disjoint.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nGenerate all subsequences using bitmasking, store lengths of palindromic ones. Compute max product by iterating over pairs of these subsequences, ensuring they\'re disjoint (bitmasks don\'t overlap).\n\n# Complexity\n- Time complexity: O(4^n) time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(2^n) space\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nNote: Time complexity is from nested iteration over 2^n size dict.\n\n# Code\n```\nclass Solution:\n    def is_palindrome(self, s: str) -> bool:\n        L, R = 0, len(s) - 1\n        while L < R:\n            if s[L] != s[R]:\n                return False\n            L += 1\n            R -= 1\n        return True\n\n    def maxProduct(self, s: str) -> int:\n        n = len(s)\n        length_pal = dict()\n\n        # Generate every possible subsequence\n        for bitmask in range(1, 2 ** n):\n            sequence = ""\n            for i in range(n):\n                if bitmask & (1 << i):\n                    sequence += s[i]\n\n            if self.is_palindrome(sequence):\n                length_pal[bitmask] = len(sequence)\n        \n        # Compute the max product \n        max_product = 0\n        for bitmask1 in length_pal:\n            for bitmask2 in length_pal:\n                # Check if masks are disjoint\n                if bitmask1 & bitmask2 == 0: \n                    max_product = max(max_product, length_pal[bitmask1] * length_pal[bitmask2])\n\n        return max_product \n\n# O(4^n) time\n# O(2^n) space\n\n```
['Python3']