[Python] Binary
Binary\n- Step 1: find all palindromic subsequences\n- Step 2: for each pair of palindromic string, if there is no disjoint, calculate the product, update the m
Binary\n- Step 1: find all palindromic subsequences\n- Step 2: for each pair of palindromic string, if there is no disjoint, calculate the product, update the max product value\n\nTips to improve performance:\nUse binary to generate all possible subsequences,\ncache both the binary represent and length of the word\nif two word binary and is zero, there is no overlap\n\nfor exampe: for word "abcd"\n\n0100 means "b"\n0010 means "c"\n\n0100 & 0010 = 0, therefore, there is no overlap\n\nsame logic\n0100 means "b"\n0110 means "bc"\n0100 & 0110 != 0, thereforem, there is overlap\n\n```\nclass Solution:\n    def maxProduct(self, s: str) -> int:\n        all_palindromic_subsequences = []\n        \n        n = len(s)\n        \n        def isPalindromic(word):\n            l, r = 0, len(word) - 1\n            while l <= r:\n                if word[l] != word[r]:\n                    return False\n                l += 1\n                r -= 1\n            return True\n        \n        for i in range(1 << n):\n            cur = ""\n            for j in range(n):\n                if i & (1 << j) != 0:\n                    cur += s[j]\n            if cur and isPalindromic(cur):\n                all_palindromic_subsequences.append((i, len(cur)))\n        \n        mx = 0\n        n = len(all_palindromic_subsequences)\n        for i in range(n):\n            for j in range(i + 1, n):\n                b1, len1 = all_palindromic_subsequences[i]\n                b2, len2 = all_palindromic_subsequences[j]\n                if b1 & b2  == 0:  \n                    cur_prod = len1 * len2\n                    mx = max(mx, cur_prod)\n        return mx\n            \n```\n
[]