Medium

题目描述

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

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

子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变相对位置而组成的新字符串。如果一个字符串从前往后读和从后往前读一样，那么这个字符串是 回文字符串 。

示例 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 只包含小写英文字母。

解题思路

这道题需要找到两个不相交的回文子序列，使得它们长度的乘积最大。由于字符串长度最大只有12，我们可以使用位掩码（bitmask）来枚举所有可能的子序列组合。

解题思路：

  1. 位掩码枚举：使用位掩码来表示子序列的选择情况，每个位表示是否选择对应位置的字符。
  2. 生成所有子序列：对于长度为n的字符串，总共有2^n种选择方式。
  3. 检查回文性：对于每个子序列，检查其是否为回文串。
  4. 寻找不相交对：两个子序列不相交意味着它们对应的位掩码按位与结果为0。
  5. 优化策略：可以预先计算所有回文子序列及其长度，然后枚举所有不相交的组合。

算法步骤：

  • 首先枚举所有可能的位掩码（1到2^n-1）
  • 对每个位掩码，构造对应的子序列并检查是否为回文
  • 将所有回文子序列的位掩码和长度存储
  • 枚举所有回文子序列对，检查是否不相交，更新最大乘积

时间复杂度主要受限于枚举所有子序列组合，由于n≤12，这种暴力方法是可行的。

代码实现

class Solution {
public:
    int maxProduct(string s) {
        int n = s.length();
        vector<pair<int, int>> palindromes; // (mask, length)
        
        // 枚举所有可能的子序列
        for (int mask = 1; mask < (1 << n); mask++) {
            string subseq = "";
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subseq += s[i];
                }
            }
            
            // 检查是否为回文
            if (isPalindrome(subseq)) {
                palindromes.push_back({mask, (int)subseq.length()});
            }
        }
        
        int maxProduct = 0;
        // 枚举所有回文子序列对
        for (int i = 0; i < palindromes.size(); i++) {
            for (int j = i + 1; j < palindromes.size(); j++) {
                // 检查是否不相交
                if ((palindromes[i].first & palindromes[j].first) == 0) {
                    maxProduct = max(maxProduct, palindromes[i].second * palindromes[j].second);
                }
            }
        }
        
        return maxProduct;
    }
    
private:
    bool isPalindrome(const string& s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        palindromes = []  # (mask, length)
        
        # 枚举所有可能的子序列
        for mask in range(1, 1 << n):
            subseq = ""
            for i in range(n):
                if mask & (1 << i):
                    subseq += s[i]
            
            # 检查是否为回文
            if subseq == subseq[::-1]:
                palindromes.append((mask, len(subseq)))
        
        max_product = 0
        # 枚举所有回文子序列对
        for i in range(len(palindromes)):
            for j in range(i + 1, len(palindromes)):
                # 检查是否不相交
                if palindromes[i][0] & palindromes[j][0] == 0:
                    max_product = max(max_product, palindromes[i][1] * palindromes[j][1])
        
        return max_product

public class Solution {
    public int MaxProduct(string s) {
        int n = s.Length;
        var palindromes = new List<(int mask, int length)>();
        
        // 枚举所有可能的子序列
        for (int mask = 1; mask < (1 << n); mask++) {
            var subseq = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subseq.Append(s[i]);
                }
            }
            
            // 检查是否为回文
            string subseqStr = subseq.ToString();
            if (IsPalindrome(subseqStr)) {
                palindromes.Add((mask, subseqStr.Length));
            }
        }
        
        int maxProduct = 0;
        // 枚举所有回文子序列对
        for (int i = 0; i < palindromes.Count; i++) {
            for (int j = i + 1; j < palindromes.Count; j++) {
                // 检查是否不相交
                if ((palindromes[i].mask & palindromes[j].mask) == 0) {
                    maxProduct = Math.Max(maxProduct, palindromes[i].length * palindromes[j].length);
                }
            }
        }
        
        return maxProduct;
    }
    
    private bool IsPalindrome(string s) {
        int left = 0, right = s.Length - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

var maxProduct = function(s) {
    const n = s.length;
    const memo = new Map();
    
    function isPalindrome(str) {
        let left = 0, right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    
    function getLongestPalindrome(mask) {
        if (memo.has(mask)) return memo.get(mask);
        
        const chars = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                chars.push(s[i]);
            }
        }
        
        const str = chars.join('');
        let maxLen = 0;
        
        // Generate all subsequences of the selected characters
        for (let subMask = mask; subMask > 0; subMask = (subMask - 1) & mask) {
            const subChars = [];
            for (let i = 0; i < n; i++) {
                if (subMask & (1 << i)) {
                    subChars.push(s[i]);
                }
            }
            const subStr = subChars.join('');
            if (isPalindrome(subStr)) {
                maxLen = Math.max(maxLen, subStr.length);
            }
        }
        
        memo.set(mask, maxLen);
        return maxLen;
    }
    
    let maxProduct = 0;
    
    // Try all possible ways to split indices into two disjoint sets
    for (let mask1 = 1; mask1 < (1 << n); mask1++) {
        for (let mask2 = 1; mask2 < (1 << n); mask2++) {
            // Check if masks are disjoint
            if ((mask1 & mask2) === 0) {
                const len1 = getLongestPalindrome(mask1);
                const len2 = getLongestPalindrome(mask2);
                maxProduct = Math.max(maxProduct, len1 * len2);
            }
        }
    }
    
    return maxProduct;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n × n + k^2)其中n为字符串长度，k为回文子序列个数。枚举所有子序列需要O(2^n)，每个子序列检查回文需要O(n)，最后枚举回文对需要O(k^2)
空间复杂度O(k)存储所有回文子序列的信息，k为回文子序列个数，最坏情况下k = O(2^n)

相关题目