2002. Maximum Product of the Length of Two Palindromic Subsequences

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

Return the maximum possible product of the lengths of the two palindromic subsequences.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

class Solution {
    bool palindrome(string s) {
        int l = 0, r = s.length() - 1;
        while(l < r) {
            if(s[l++] != s[r--]) return false;
        }
        return true;
    }
public:
    int maxProduct(string s) {
        int res = 0, n = s.length();
        vector<int> mask;
        for(int sub = 1; sub < 1<<n; sub++) {
            string now = "";
            for(int i = 0; i < n; i++) {
                if(sub & (1<<i)) now.push_back(s[i]);
            }
            if(palindrome(now)) mask.push_back(sub);
        }
        for(int i = 0; i < mask.size(); i++) {
            for(int j = i + 1; j < mask.size(); j++) {
                if(mask[i] & mask[j]) continue;
                res = max(res, __builtin_popcount(mask[i]) * __builtin_popcount(mask[j]));
            }
        }
        return res;
    }
};