C++ || Backtracking Solution || Intuition Explained
Intuition:\n\nIdea is to form all combinations of subsequences that are palindromic, that are not overlapping i.e first string and second string should not have
**Intuition:**\n\nIdea is to form all combinations of subsequences that are palindromic, that are not overlapping i.e *first* string and *second* string should not have any common element from main string. Out of all possible *first* and *second* strings, we find product of `first.size() * second.size()` . In the end we return the maximum product. \n\nNext, looking at the size of given string i.e `1 <= n <= 12`. We can do a brute force over it and use **Backtracking** to get all possible combinations of *first* and *second* string that are subsequences of original string. \n\nNow, lets see how can we form *first* and *second* string? Think of possible choices at every index of the original string. What can we pick and what we can skip. Since, we are given that both the palindromic should not have any common element (non-overlapping and disjoint). Thus, we cannot include current element in both strings simultaneously.\n\nSo, we have actually 3 choices at every index.\n1. Exclude the current element from both *first* and *second* string. \n\n2. Include the current element into *first* string  -> Backtracking, **include -> use -> remove**\n\n3. Include the current element into *second* string.  -> Backtracking, **include -> use -> remove**\n\n**Base Condition :** : When we reach the end of string, check if first and second string are palindrome or not. \n* If not then return \n* Else calculate the product of lengths `first.size() * second.size()` and update maximumProduct accordingly\n \nGo through the code, it is self explainatory and easy to understand. Just simple backtracking logic, nothing complex. \n\nNote: We are passing first and second strings by **reference**, so that in every function call new copies of string is not created. If we do not consider this, it will give a TLE. \n\n# Code : \n```\nint maxProd = 1, n;\n    bool isPalindrome(const string& s)\n    {\n        int n = s.size();\n        for(int i=0; i<n/2; i++)\n            if(s[i] != s[n-1-i]) return false;\n        return true;\n    }\n    \n    void solve(string& s, string& first, string& second, int idx)\n    {\n        if(idx == n) \n        {\n\t\t\t// Check if both strings are palindrome or not\n\t\t\t// If yes, then find product or their lengths\n            if(isPalindrome(first) && isPalindrome(second))         \n            {\n                maxProd = max(maxProd, (int)(first.size() * second.size()));\n            }\n            return;\n        }\n        \n        // Choice 1 : Exclude current element from both strings\n        solve(s, first, second, idx+1);\n        \n        // Choice 2 : Include current element into first string\n        first.push_back(s[idx]);\n        solve(s, first, second, idx+1);\n        first.pop_back();\n        \n        // Choice 3 : Include current element into second string\n        second.push_back(s[idx]);\n        solve(s, first, second, idx+1);\n        second.pop_back();\n    }\n    \n    int maxProduct(string s) {\n        n = s.size();\n        string first = "", second = "";\n        solve(s, first, second, 0);                              // Start from 0th index\n        return maxProd;\n    }\n```\n\n**Time : O(n * 3^n)** \n* In each recursive call we have 3 choices so total **O(3^n)**\n* and **O(n)** to check if both strings are palindrome or not \n\n***If you find this solution helpful, do give it an upvote :)***
['Backtracking', 'Recursion']