MOST SIMPLE KNAPSACK SOLUTION EVER ON INTERNET: most of you thought, must be a hard question but see
Intuition\njust simple knapsack : make two empty string s1 and s2 and at each element you have three options :\n1. add element to s1 \n2. add element to s2\n3. 
# Intuition\njust simple knapsack : make two empty string s1 and s2 and at each element you have three options :\n1. add element to s1 \n2. add element to s2\n3. add element to none of them \n\nat the base case: if(index==s.size()){\n            if(s1.size() and s2.size() and ispalindrome(s1) and ispalindrome(s2)){\n                return s1.size()*s2.size();\n            }\n            return 0;\n        }\n\n# Approach\nknapsack\n\n# Complexity\n- Time complexity:\nO(n^2) even after memoization\n\n- Space complexity:\no(n);\n\n# Code\n# whatsapp me if it worked: 6209554569\n```cpp []\nclass Solution {\npublic:\n    bool ispalindrome(string s1){\n        string a=s1;;\n        reverse(s1.begin(),s1.end());\n      \n        return a==s1;\n    }\n    unordered_map<string,int>maps;\n    int find(string&s,int index,string s1,string s2){\n        if(index==s.size()){\n            if(s1.size() and s2.size() and ispalindrome(s1) and ispalindrome(s2)){\n                return s1.size()*s2.size();\n            }\n            return 0;\n        }\n        string key=to_string(index)+","+s1+","+s2;\n        if(maps.find(key)!=maps.end()){\n            return maps[key];\n        }\n        // go with s1 \n        int a=find(s,index+1,s1+s[index],s2);\n        // go with s2\n        int b=find(s,index+1,s1,s2+s[index]);\n        // go with none \n        int c=find(s,index+1,s1,s2);\n        return maps[key]=max(a,max(b,c));\n    }\n    int maxProduct(string&s) {\n        \n        return find(s,0,"","");\n    }\n};\n```
['Dynamic Programming', 'C++']