LeetCode 2002. 两个回文子序列长度的最大乘积（状态压缩+枚举状态子集+预处理）

输入：s = "leetcodecom"
输出：9
解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。

示例 2：
输入：s = "bb"
输出：1
解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。

示例 3：
输入：s = "accbcaxxcxx"
输出：25
解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。
 
提示：
2 <= s.length <= 12
s 只含有小写英文字母。

class Solution {
public:
    int maxProduct(string s) {
        int n = s.size();
        int ans = 1, state = (1<<n)-1;
        for(int i = state; i; i=state&(i-1))
        {
            int left = ~i&state;
            for(int k = left; k; k=left&(k-1))
                ans = max(ans, process(s, i)*process(s, k));
        }
        return ans;
    }
    int process(string& s, int num)
    {
        int n = s.size();
        string t;
        for(int i = 0; i < n; ++i)
        {
            if(num&(1<<i))
                t.push_back(s[i]);
        }
        int ans = 0, i = 0, j = int(t.size())-1;
        while(i < j)
        {
            if(t[i] == t[j])
            {
                i++, j--;
                ans += 2;
            }
            else
                break;
        }
        if(i < j) return 0;
        if(i == j) return ans+1;
        else return ans;
    }
};

class Solution {
public:
    int maxProduct(string s) {
        int n = s.size();
        vector<int> palind = process(s);
        int ans = 1, state = (1<<n)-1;
        for(int i = state; i; i=state&(i-1))
        {
            int left = ~i&state;
            for(int k = left; k; k=left&(k-1))
                ans = max(ans, palind[i]*palind[k]);
        }
        return ans;
    }
    vector<int> process(string& s)
    {
        int n = s.size();
        vector<int> palind(1<<n, 0); 
        for(int state = (1<<n)-1; state; state--)
        {
            string t;
            for(int i = 0; i < n; ++i)
            {
                if(state&(1<<i))
                    t.push_back(s[i]);
            }
            int ans = 0, i = 0, j = int(t.size())-1;
            while(i < j)
            {
                if(t[i] == t[j])
                {
                    i++, j--;
                    ans += 2;
                }
                else
                    break;
            }
            if(i < j) ;
            if(i == j) palind[state] = ans+1;
            else palind[state] = ans;
        }
        return palind;
    }
};