[C++] Brute force + DP explanation
Approach: \nstep1: Generate all subsequence in O(2^n) time (Note: we are storing indices not the characters while generating subsequence)\nstep2: Suppose one of
**Approach:** \n*step1:* Generate all subsequence in O(2^n) time (Note: we are storing indices not the characters while generating subsequence)\n*step2:* Suppose one of the above subsequence is X. now first check if X is palindrome or not\n*step3:* If X is palindrome. Then get the remaining string i.e by deleting characters included in X from original string s in O(n) (as we know indices of character in X)\n*step 4:* from remaining string calculated above, find the length of longest palindromic subsequence present in it, which can be done in O(n^2) using Dynamic programming.\n\nOverall Time complexity is : O(2^n *n^2) \nwhich is good enough for n=12.  \n\n```\nclass Solution {\n    private:\n    int ans; //to store final ans\n    \n    int max (int x, int y) { return (x > y)? x : y; }\n \n    //find longest palindromic subsequence  [Time:(O(n^2))]\n    int lps(string& str)\n    {\n       int n = str.length();\n       if(n<=1)return n;\n       int i, j, cl;\n       int L[n][n];  // Create a table to store results of subproblems\n\n       // Strings of length 1 are palindrome of length 1\n       for (i = 0; i < n; i++)\n          L[i][i] = 1;\n        for (cl=2; cl<=n; cl++){\n            for (i=0; i<n-cl+1; i++){\n                j = i+cl-1;\n                if (str[i] == str[j] && cl == 2)\n                   L[i][j] = 2;\n                else if (str[i] == str[j])\n                   L[i][j] = L[i+1][j-1] + 2;\n                else\n                   L[i][j] = max(L[i][j-1], L[i+1][j]);\n            }\n        }\n\n        return L[0][n-1];\n    }\n    \n    \n    bool isPal(string &x,vector<int>&v){  //check using indices present in v if they represent a palindromic sequence \n        int l=0,h=v.size()-1;\n        while(l<=h){\n            if(x[v[l]]!=x[v[h]])return false;\n            l++;\n            h--;\n        }\n        return true;\n    }\n    \n    \n    void check(string &s,vector<int>&v){\n        if((v.size()>0)&&(v.size()<s.size())&&!isPal(s,v))return;  //return if indices present in vector v doesn\'t form a palindrome\n        \n        string res="";                  //in res store all characters which are not included in vector v\n        unordered_map<int,int> mp;\n        for(auto i:v)mp[i]++;\n        for(int i=0;i<s.length();i++){\n            if(mp.count(i)==0)res+=s[i];\n        }\n        \n        int l1=v.size();  \n        int l2=lps(res); //get the length of longest palindromic subsequence present in res\n        int currAns=l1*l2;\n        ans=max(ans,currAns); //update ans\n    }\n    \n    \n    //Get all possible subsequence indicies in vector v  [Time:(O(2^n))]\n    void generateSequence(string &s,int i,vector<int> v){\n        if(i==s.length()){\n           check(s,v);  //check for possible result\n            return;\n        }\n        \n        generateSequence(s,i+1,v);  //don\'t include current character \n        v.push_back(i);\n        generateSequence(s,i+1,v);  //include current character\n       \n    }\n    \npublic:\n    int maxProduct(string s) {\n        ans=0; //initialize ans\n        vector<int> v;\n        generateSequence(s,0,v);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C']