DP || Bitmask || Recurssion || C++|| ✅94.18% Beats✅||
Intuition\n Describe your first thoughts on how to solve this problem. \n- Initially check all LCS in the string.\n- Create a mask of every LCS possible.\n- Usi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Initially check all LCS in the string.\n- Create a mask of every LCS possible.\n- Using the mask take the LCS of unset indexes.\n- Then take the maximum of the product of both for each LCS. \n\n# Code\n```\nclass Solution {\npublic:\n    int ans = 0;\n    int dp[1<<12][12][12];\n    int help(string &s, int i, int j, int mask){\n        if(i >= j){\n            if(i == j && !(mask&(1<<i)))\n                return 1;\n            return 0;\n        }\n        \n        if(dp[mask][i][j] != -1)\n            return dp[mask][i][j];\n\n        int a = 0;\n        if((mask&(1<<i)) || (mask&(1<<j))){\n            if((mask&(1<<i)))\n                a = max(a, help(s, i+1, j, mask));\n            if(mask&(1<<j))\n                a = max(a, help(s, i, j-1, mask));\n        }\n        else{\n            if(s[i] == s[j])\n                a = max(a, help(s, i+1, j-1, mask) + 2); \n            a = max(a, help(s, i+1, j, mask));\n            a = max(a, help(s, i, j-1, mask));\n        }\n\n        return dp[mask][i][j] = a;\n    }\n    void solve(string &s, int i, int j, int len, int mask){\n        if(i >= j){\n            int a = 0, n = 0;\n            if(i == j){\n                a = 1;\n                n = n | (1<<i);\n            }\n            if((mask | n) != (1<<s.length())-1)\n                ans = max(ans, (len + a)*help(s, 0, s.length()-1, mask|n));\n            if(mask != (1<<s.length())-1)\n                ans = max(ans, len*help(s, 0, s.length()-1, mask));\n\n            return ;\n        }\n        \n        if(s[i] == s[j]){\n            int n = 0;\n            n = n | (1<<i);\n            n = n | (1<<j);\n            solve(s, i+1, j-1, len+2, mask | n);\n        }\n\n        solve(s, i+1, j, len, mask);\n        solve(s, i, j-1, len, mask);\n\n        return;\n    }\n    int maxProduct(string s) {\n        int mask = 0;\n        memset(dp, -1, sizeof dp);\n        solve(s, 0, s.length()-1, 0, mask);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'Recursion', 'Bitmask', 'C++']