Mask DP
We have 2^n possible palindromes, and each of them can be represented by a mask [1 ... 4096] (since n is limited to 12).\n\nFirst, we check if a mask represents
We have `2^n` possible palindromes, and each of them can be represented by a mask `[1 ... 4096]` (since `n` is limited to `12`).\n\nFirst, we check if a mask represents a valid palindrome, and if so, store the length (or, number of `1` bits) in `dp`.\n\nThen, we check all non-zero masks `m1` against all non-intersecting masks `m2` (`m1 & m2 == 0`), and track the largest product.\n\n>Update1: as suggested by [Gowe](https://leetcode.com/Gowe/), we can use more efficient enumeration for `m2` to only go through "available" bits (`mask ^ m1`). This speeds up C++ runtime from 44 to 22 ms!\n\n> Update 2: we can do pruning to skip masks with no potential to surpass the current maximum. The runtime is now reduced to 4ms!\n\n> Update 3: an alternative solution (proposed by [LVL99](https://leetcode.com/LVL99/)) is to not check all submasks, but instead run "Largest Palindromic Subsequence" algo for all unused bits. This potentially can reduce checks from `2 ^ n` to `n ^ 2`. It\'s a longer solution, so posted it as a comment.\n\n**C++**\n```cpp\nint palSize(string &s, int mask) {\n    int p1 = 0, p2 = s.size(), res = 0;\n    while (p1 <= p2) {\n        if ((mask & (1 << p1)) == 0)\n            ++p1;\n        else if ((mask & (1 << p2)) == 0)\n            --p2;\n        else if (s[p1] != s[p2])\n            return 0;\n        else\n            res += 1 + (p1++ != p2--);\n    }\n    return res;\n}\nint maxProduct(string s) {\n    int dp[4096] = {}, res = 0, mask = (1 << s.size()) - 1;\n    for (int m = 1; m <= mask; ++m)\n        dp[m] = palSize(s, m);\n    for (int m1 = mask; m1; --m1)\n        if (dp[m1] * (s.size() - dp[m1]) > res)\n            for(int m2 = mask ^ m1; m2; m2 = (m2 - 1) & (mask ^ m1))\n                res = max(res, dp[m1] * dp[m2]);\n    return res;\n}\n```\n**Java**\nJava version courtesy of [amoghtewari](https://leetcode.com/amoghtewari/).\n```java\npublic int maxProduct(String s) {\n    int[] dp = new int[4096];\n    int res = 0, mask = (1 << s.length()) - 1;\n    for (int m = 1; m <= mask; ++m)\n        dp[m] = palSize(s, m);\n    for (int m1 = mask; m1 > 0; --m1)\n        if (dp[m1] * (s.length() - dp[m1]) > res)\n            for(int m2 = mask ^ m1; m2 > 0; m2 = (m2 - 1) & (mask ^ m1))\n                res = Math.max(res, dp[m1] * dp[m2]);\n    return res;\n}\nprivate int palSize(String s, int mask) {\n    int p1 = 0, p2 = s.length(), res = 0;\n    while (p1 <= p2) {\n        if ((mask & (1 << p1)) == 0)\n            ++p1;\n        else if ((mask & (1 << p2)) == 0)\n            --p2;\n        else if (s.charAt(p1) != s.charAt(p2))\n            return 0;\n        else\n            res += 1 + (p1++ != p2-- ? 1 : 0);\n    }\n    return res;\n}\n```
['C', 'Java']