Easy to understand Solution | Bitmask | Brute force
Intuition\nThe problem is asking for the maximum product of the lengths of two non-overlapping palindromic subsequences. The key observation is that palindromic
# Intuition\nThe problem is asking for the maximum product of the lengths of two non-overlapping palindromic subsequences. The key observation is that palindromic subsequences can be generated using bitmasks, and if we check for all possible pairs of subsequences, we can identify those that are non-overlapping and have the largest product of their lengths.\n\n# Approach\n1. **Bitmask Representation for Subsequence Generation:**\nEach subsequence of the given string can be represented using a bitmask. For a string of length n, there are \n2^n possible subsequences. Each bit in the bitmask represents whether a character at a particular position is included in the subsequence or not.\n\n2. **Generating Subsequences and Checking Palindromes:**\nFor each bitmask, generate the corresponding subsequence. Then, check if this subsequence is a palindrome by comparing it with its reverse. Store the length of this palindromic subsequence using the bitmask as the key in a map.\n\n3. **Checking Non-Overlapping Subsequences:**\nFor each pair of palindromic subsequences, check if they are non-overlapping by ensuring that the bitwise AND of their bitmasks is 0. If they are non-overlapping, compute the product of their lengths and update the result if it\u2019s the maximum found so far.\n\n# Complexity\n- Time complexity:\n    * Generating all subsequences takes \uD835\uDC42((2^\uD835\uDC5B).\uD835\uDC5B), where \uD835\uDC5B is the length of the string.\n    * Checking each pair of subsequences for overlap takes \n\uD835\uDC42((2^\uD835\uDC5B).(2^\uD835\uDC5B))in the worst case.\n    * Therefore, the overall time complexity is \uD835\uDC42((4^\uD835\uDC5B)+(2^\uD835\uDC5B)\u22C5\uD835\uDC5B), which is feasible for small strings (e.g., \uD835\uDC5B\u226412).\n\n- Space complexity:\nThe space complexity is \uD835\uDC42(2\uD835\uDC5B) due to the storage of subsequences in the map.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxProduct(string s) {\n        unordered_map<int, int> mp;\n        int n = s.size();\n\n        // Generate all subsequences using bitmasks\n        for(int i = 0; i < (1 << n); i++){\n            string subseq;\n            for(int j = 0; j < n; j++){\n                if(i & (1 << j)){\n                    subseq.push_back(s[j]);\n                }   \n            }\n            string rev = subseq;\n            reverse(rev.begin(), rev.end());\n\n            // If the subsequence is a palindrome, store its length\n            if(subseq == rev){\n                mp[i] = subseq.size();\n            }\n        }\n\n        int res = 0;\n\n        // Iterate over all pairs of subsequences\n        for(auto& i : mp){\n            for(auto& j : mp){\n                // Ensure the two subsequences don\'t overlap\n                if((i.first & j.first) == 0){\n                    res = max(res, i.second * j.second);\n                }\n            }\n        }\n\n        return res;\n    }\n};\n\n```
['Hash Table', 'Bitmask', 'C++']