All 3 Solutions | Brute | Optimizations | Clean and Concise | Bits
1. Using Bits as a visitied array total brute force\n\n\nclass Solution {\npublic:\n    bool check(string &s){\n        int i=0,j=s.size()-1;\n        \n       
#### **1. Using Bits as a visitied array total brute force**\n\n```\nclass Solution {\npublic:\n    bool check(string &s){\n        int i=0,j=s.size()-1;\n        \n        while(i < j){\n            if(s[i] != s[j])  return false;\n            i++;\n            j--;\n        }\n        return true;\n    }\n    int fun2(int i,int vis_,int vis,string &s){\n        \n        if(i == s.size()){\n            \n            string tmp;\n            \n            for(int i=0;i<s.size();i++){\n                int mask = (1 << i);\n                if((mask & vis_) != 0){\n                    tmp.push_back(s[i]);\n                }\n            }\n            if(check(tmp)) return tmp.size();\n            return 0;\n        }\n        \n        \n        int mask = (1 << i);\n        \n        if((mask & vis) == 0){\n            int left = fun2(i+1,vis_|mask,vis|mask,s);\n            int right = fun2(i+1,vis_,vis,s);\n            return max(left,right);\n        }\n        return fun2(i+1,vis_,vis,s);\n    }\n    \n    int fun1(int i,int vis,string &s){\n        \n        int n = s.size();\n        if(i == n){\n            \n            int len = fun2(0,0,vis,s);\n            \n            string tmp;\n            \n            for(int i=0;i<s.size();i++){\n                int mask = (1 << i);\n                if((mask & vis) != 0){\n                    tmp.push_back(s[i]);\n                }\n            }\n            if(check(tmp)){\n                return (len)*(tmp.size());   \n            }\n            return 0;\n        } \n        \n        \n        int mask = (1 << i);\n        int left = fun1(i+1,mask | vis,s);\n        int right = fun1(i+1,vis,s);\n        \n        return max(left,right);\n    \n    }\n    \n    int maxProduct(string s) {\n        return fun1(0,0,s);\n        \n    }\n\t\n```\n\n### 2. Using Longest Common Subsequence\n\n```\n\tclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int LCS(int i,int j,string &s1,string &s2){\n        \n        int n1 = s1.size();\n        int n2 = s2.size();\n        \n        if(i == n1 or j == n2){\n            return 0;\n        }\n        if(dp[i][j] != -1) return dp[i][j];\n        if(s1[i] == s2[j]){\n            return dp[i][j] = 1 + LCS(i+1,j+1,s1,s2);\n        }\n        \n        return dp[i][j] = max(LCS(i+1,j,s1,s2),LCS(i,j+1,s1,s2));\n        \n    }\n    \n    int LPS(string &s){\n        string t = s;\n        reverse(s.begin(),s.end());\n        dp = vector<vector<int>> (s.size(),vector<int> (s.size(),-1));\n        return LCS(0,0,s,t);\n    }\n\n    int fun1(int i,int vis,string &s){\n        \n        int n = s.size();\n        if(i == n){\n            string s1,s2;\n            for(int j=0;j<n;j++){\n                int mask = (1 << j);\n                if((vis & mask ) == 0){\n                    s2.push_back(s[j]);\n                }else{\n                    s1.push_back(s[j]);\n                }\n            }        \n            return LPS(s1)*LPS(s2);\n        } \n        \n        int mask = (1 << i);\n        int left = fun1(i+1,mask | vis,s);\n        int right = fun1(i+1,vis,s);\n        \n        return max(left,right);\n    \n    }\n    \n    int maxProduct(string s) {\n        int n = s.size();\n        return fun1(0,0,s);\n    }\n};\n\n```\n\n### 3. Using Longest Palindromic Subsequence\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    \n    int LPS_(int i,int j,string &s){\n        \n        if(i > j) return 0;\n        if(i==j) return 1;\n        if(dp[i][j] != -1) return dp[i][j];\n        if(s[i] == s[j]){\n            return dp[i][j] = 2 + LPS_(i+1,j-1,s);\n        }\n        return dp[i][j] = max(LPS_(i+1,j,s),LPS_(i,j-1,s));\n    }\n    \n    int LPS(string &s){\n        dp = vector<vector<int>> (s.size(),vector<int> (s.size(),-1));\n        return LPS_(0,s.size()-1,s);\n    }\n\n    int fun1(int i,int vis,string &s){\n        \n        int n = s.size();\n        if(i == n){\n            string s1,s2;\n            for(int j=0;j<n;j++){\n                int mask = (1 << j);\n                if((vis & mask ) == 0){\n                    s2.push_back(s[j]);\n                }else{\n                    s1.push_back(s[j]);\n                }\n            }        \n            return LPS(s1)*LPS(s2);\n        } \n        \n        int mask = (1 << i);\n        int left = fun1(i+1,mask | vis,s);\n        int right = fun1(i+1,vis,s);\n        \n        return max(left,right);\n    \n    }\n    \n    int maxProduct(string s) {\n        int n = s.size();\n        return fun1(0,0,s);\n    }\n};\n\t\n};
['Dynamic Programming', 'Recursion']