两个回文子序列长度的最大乘积 图解题解

两个回文子序列不相交，到底在挑什么

从 s 里挑两个子序列（删掉若干字符、剩下保持原顺序），各自是回文（正读反读一样），互不相交——同一个下标不能两边都用，求长度乘积最大。题面 leetcodecom 里 ete（下标 1、3、7）配 cdc（4、6、8），零重叠，3×3=9。s 长度顶多 12，是整道题的方向盘。

先抢一条最长回文，为什么会亏

先拿一条最长回文、剩下再取第二条，在题面 accbcaxxcxx 上露馅：长 5 的最长回文不止一条——取 accca，剩下恰好凑出 xxcxx，5×5=25；取 ccbcc 就抢走了 xxcxx 中间那个 c，最多剩 xxxx，5×4=20。

每个下标三个去处（进第一条、进第二条、不用），3¹²≈53 万种分法，机器一眨眼；别硬套 DP（动态规划，把「区间内最长回文多长」存表复用，这题数得完，用不上），枚举就是正解。

选了哪些下标，怎么塞进一个整数里

用位掩码记「选了哪些下标」：整数二进制第 i 位是 1 表示选中下标 i，掩码最右一位对应下标 0，4095 个掩码（n=12 时从 1 数到 2¹²−1=4095）扫遍全部非空子集，这套压法就是状态压缩。两件事变简单：m1 & m2 == 0（没有一位同时是 1）就是两组下标不共用；掩码里 1 的个数就是子序列长度。

参考代码先开布尔表 p，对每个掩码 k 用两端指针验回文：为 0 的位直接跳过，撞上 s[i] != s[j] 就记 p[k] = False。

第二条为什么只能去补集里挑

对每个回文掩码 i，第二条只从补集 mx = ((1 << n) - 1) ^ i（1<<n 是把 1 左移 n 位；(1<<n)−1 就是 n 位全 1；^ 是异或——把 i 里是 1 的位翻成 0，得到补集）里挑：从中选的子掩码天然不和 i 相交。枚举从 j = mx 开始，每步 j = (j - 1) & mx，把减 1 后越出补集的位掐掉，不重不漏扫完全部子集，p[j] 为真就拿两边 1 的个数相乘更新答案。

bb 的三个掩码各自长什么样

题面 s = bb 只有三个掩码：01 选出单个 b，单字符自然回文，p[01] 为真；10 同理；11 选出 bb，两端都是 b，也为真。

配对：第一条取 01 时补集 mx=10，j 从 10 起步，p[10] 为真，1×1=1 记进答案；再走 j=(10-1)&10=00 结束。第一条取 10 时补集是 01，同样得 1。取 11 时补集是 00：整串占满，另一条只能空着。答案 1，对上题面。

子掩码枚举漏了与上 mx，会把哪些非法配对数进来

把 j = (j - 1) & mx 写成裸的 j = j - 1，会把和 i 抢下标的掩码也数进候选，答案跟着变大。空集天然被挡在外：j 从 mx 起步、条件 j 非零；n≥2 时答案至少 1，两个单字符各占一位就是一对。

验回文一步扫 2ⁿ 个掩码、每个指针走 O(n)（大 O，衡量数据变大时操作量怎么涨）；配对的子掩码总数是 3ⁿ，还是三个去处那笔账。合计 O(3ⁿ + 2ⁿ·n)，空间是布尔表 O(2ⁿ)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        p = [True] * (1 << n)
        for k in range(1, 1 << n):
            i, j = 0, n - 1
            while i < j:
                while i < j and (k >> i & 1) == 0:
                    i += 1
                while i < j and (k >> j & 1) == 0:
                    j -= 1
                if i < j and s[i] != s[j]:
                    p[k] = False
                    break
                i, j = i + 1, j - 1
        ans = 0
        for i in range(1, 1 << n):
            if p[i]:
                mx = ((1 << n) - 1) ^ i
                j = mx
                a = i.bit_count()
                while j:
                    if p[j]:
                        b = j.bit_count()
                        ans = max(ans, a * b)
                    j = (j - 1) & mx
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxProduct(string s) {
        int n = s.size();
        vector<bool> p(1 << n, true);
        for (int k = 1; k < 1 << n; ++k) {
            for (int i = 0, j = n - 1; i < j; ++i, --j) {
                while (i < j && !(k >> i & 1)) {
                    ++i;
                }
                while (i < j && !(k >> j & 1)) {
                    --j;
                }
                if (i < j && s[i] != s[j]) {
                    p[k] = false;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 1 << n; ++i) {
            if (p[i]) {
                int a = __builtin_popcount(i);
                int mx = ((1 << n) - 1) ^ i;
                for (int j = mx; j; j = (j - 1) & mx) {
                    if (p[j]) {
                        int b = __builtin_popcount(j);
                        ans = max(ans, a * b);
                    }
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        boolean[] p = new boolean[1 << n];
        Arrays.fill(p, true);
        for (int k = 1; k < 1 << n; ++k) {
            for (int i = 0, j = n - 1; i < n; ++i, --j) {
                while (i < j && (k >> i & 1) == 0) {
                    ++i;
                }
                while (i < j && (k >> j & 1) == 0) {
                    --j;
                }
                if (i < j && s.charAt(i) != s.charAt(j)) {
                    p[k] = false;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 1 << n; ++i) {
            if (p[i]) {
                int a = Integer.bitCount(i);
                int mx = ((1 << n) - 1) ^ i;
                for (int j = mx; j > 0; j = (j - 1) & mx) {
                    if (p[j]) {
                        int b = Integer.bitCount(j);
                        ans = Math.max(ans, a * b);
                    }
                }
            }
        }
        return ans;
    }
}