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

难度: Medium

给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。

请你返回两个回文子序列长度可以达到的 最大乘积 。

子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。

示例 1：

example-1

输入：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 只含有小写英文字母。

Submission

运行时间: 84 ms

内存: 16.7 MB

class Solution:
    def maxProduct(self, s: str) -> int:
        N = len(s)
        ALL = (1 << N)-1
        dp = [0]*(1 << N)  # max pal len of masked s
        pals = []
        for mask in range(1, len(dp)):
            lsb = (1 + (mask ^ (mask-1))) >> 1
            i = lsb.bit_length()-1  # lsb pos
            j = mask.bit_length()-1  # msb pos. msb is 1<<j
            if i == j:
                dp[mask] = 1
            else:
                if s[i] == s[j]:
                    dp[mask] = dp[mask ^ lsb ^ (1 << j)]+2
                else:
                    dp[mask] = max(dp[mask ^ lsb], dp[mask ^ (1 << j)])
            if dp[mask] == mask.bit_count():  # masked str is pal
                pals.append(mask)

        return max(dp[mask]*dp[mask ^ ALL] for mask in pals)

Explain

这个题解采用了位掩码和动态规划的方法来解决问题。每个位掩码代表一个字符串的子集，其中掩码的二进制位如果是1，则表示该位置的字符被包含在子序列中。算法首先计算了所有可能的子序列的最长回文长度，这是通过动态规划实现的。动态规划数组 `dp[mask]` 存储的是对于掩码 `mask` 表示的子序列的最长回文长度。在填充 `dp` 数组的过程中，同时收集所有的回文子序列掩码到列表 `pals` 中。最后，算法通过遍历所有回文子序列掩码，并计算两个不相交的回文子序列的长度乘积的最大值。这是通过对每个回文子序列掩码 `mask` 使用其补码 `mask ^ ALL` 来获得不相交的子序列，然后计算乘积 `dp[mask] * dp[mask ^ ALL]` 来实现的。

时间复杂度: O(2^N)

空间复杂度: O(2^N)

class Solution:
    def maxProduct(self, s: str) -> int:
        N = len(s)
        ALL = (1 << N)-1  # 所有位都是1的掩码
        dp = [0]*(1 << N)  # max pal len of masked s
        pals = []
        for mask in range(1, len(dp)):
            lsb = (1 + (mask ^ (mask-1))) >> 1  # 最低位的1
            i = lsb.bit_length()-1  # 最低位1的位置
            j = mask.bit_length()-1  # 最高位1的位置. msb is 1<<j
            if i == j:
                dp[mask] = 1  # 单字符回文
            else:
                if s[i] == s[j]:
                    dp[mask] = dp[mask ^ lsb ^ (1 << j)]+2  # 如果两端字符相同，中间部分的最长回文长度+2
                else:
                    dp[mask] = max(dp[mask ^ lsb], dp[mask ^ (1 << j)])  # 选择两端中的最大值
            if dp[mask] == mask.bit_count():  # 如果该掩码表示的子序列是回文
                pals.append(mask)
        return max(dp[mask]*dp[mask ^ ALL] for mask in pals) # 计算两个不相交的回文子序列的最大乘积

Explore

位掩码在表示字符串子序列时的主要优势是其高效的数据表示和操作能力。每个位掩码都是一个二进制数，其中每一位的0或1代表对应位置的字符是否被包含在子序列中。这种表示方式使得子序列的选择和修改（如添加或移除字符）可以通过简单的位运算（如AND, OR, XOR）来实现，大大提高了算法的效率。此外，使用位掩码可以方便地枚举字符串的所有可能的子序列，因为每个掩码直接对应于一个子序列。

在计算最长回文子序列的长度时，考虑最高位和最低位的字符是否相等是因为回文序列的定义是从前向后读和从后向前读都相同。因此，如果一个子序列的最高位和最低位字符相等，这两个字符可以作为回文序列的两端，然后可以继续考察去掉这两个字符后的子序列是否为回文，从而递归地构建更长的回文序列。如果最高位和最低位的字符不相等，则这两个字符不能同时出现在同一个回文序列的两端，需要分别考虑包含其中一个字符的子序列的最长回文长度。

在动态规划部分，`dp[mask]`表示为掩码`mask`对应的子序列的最长回文长度。更新`dp[mask]`的过程涉及到判断子序列的首尾字符（即最高位和最低位字符）。如果这两个字符相等，表示它们可以成为回文序列的两端。`mask ^ lsb ^ (1 << j)`是将`mask`中最低位和最高位的1翻转成0，即移除子序列中的首尾字符，因此`dp[mask ^ lsb ^ (1 << j)]`代表去掉首尾字符后的子序列的最长回文长度。因此，`dp[mask] = dp[mask ^ lsb ^ (1 << j)] + 2`这一步骤的含义是，如果当前掩码对应的子序列的首尾字符相等，其最长回文长度可以通过去掉首尾字符后的最长回文长度加2来得到。这里加2是因为首尾两个相等的字符各自增加了1的长度。