Dp in Python
We may use dp to enumerate the first palindromic sequence. Since the maximum length of the original string is only 12 - the iteration goes up to 2**12=4096 time
We may use dp to enumerate the first palindromic sequence. Since the maximum length of the original string is only 12 - the iteration goes up to `2**12=4096` times. Actually, small sized problem should always remind you to think about brute force.\n\nAfter that, just try to find the longest palindromic subsequence in the rest characters. That\'s a classic problem. You can find the exact same problem here https://leetcode.com/problems/longest-palindromic-subsequence/.\n```\nclass Solution:\n    def maxPalindrome(self, s):\n        n = len(s)\n        dp = [[0] * n for _ in range(n)]\n        for i in range(n):\n            dp[i][i] = 1\n        for i in range(n - 1, -1, -1):\n            for j in range(i + 1, n):\n                if s[i] == s[j]:\n                    dp[i][j] = dp[i+1][j-1]+2\n                else:\n                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n        return dp[0][n-1]\n\n    def maxProduct(self, s: str) -> int:\n        ans = 1\n        for i in range(1, 2**len(s)+1):\n            first = \'\'\n            remain = \'\'\n            for j in range(len(s)):\n                if i & (2**j):\n                    first += s[j]\n                else:\n                    remain += s[j]\n            if first != first[::-1] or not remain:\n                continue\n            ans = max(ans, len(first) * self.maxPalindrome(remain))\n        return ans\n```
[]