原文链接: https://leetcode-cn.com/problems/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.

 

Example 1:

Input: s = "leetcodecom"
Output: 9
Explanation: An optimal solution is to choose "ete" for the 1st subsequence and "cdc" for the 2nd subsequence.
The product of their lengths is: 3 * 3 = 9.

Example 2:

Input: s = "bb"
Output: 1
Explanation: An optimal solution is to choose "b" (the first character) for the 1st subsequence and "b" (the second character) for the 2nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Example 3:

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "accca" for the 1st subsequence and "xxcxx" for the 2nd subsequence.
The product of their lengths is: 5 * 5 = 25.

 

Constraints:

• 2 <= s.length <= 12
• s consists of lowercase English letters only.

中文题目

给你一个字符串 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 只含有小写英文字母。

通过代码

高赞题解

对于位置i，两个子序列可以选择用或者不用

暴力做法，其它语言没准会超时。

class Solution {
public:
    int ans = 0;
    int maxProduct(string s) {
        string s1, s2;
        dfs(s, s1, s2, 0);
        return ans;
    }
    
    void dfs(string &s, string s1, string s2, int index) {
        if(check(s1) && check(s2)) ans = max(ans, int(s1.size() * s2.size()));
        if(index == s.size()) return;
        dfs(s, s1 + s[index], s2, index + 1);//子序列s1使用该字符
        dfs(s, s1, s2 + s[index], index + 1);//子序列s2使用该字符
        dfs(s, s1, s2, index + 1);//子序列都不使用该字符
    }
    
    bool check(string &s) {
        int l = 0, r = s.size() - 1;
        while(l < r) {
            if(s[l++] != s[r--]) return false;
        }
        return true;
    }
};

使用引用传递加快速度：

void dfs(string &s, string &s1, string &s2, int index) {
    if(check(s1) && check(s2)) ans = max(ans, int(s1.size() * s2.size()));
    if(index == s.size()) return;
    s1.push_back(s[index]);
    dfs(s, s1, s2, index + 1);
    s1.pop_back();
    s2.push_back(s[index]);
    dfs(s, s1, s2, index + 1);
    s2.pop_back();
    dfs(s, s1, s2, index + 1);
}

统计信息

通过次数	提交次数	AC比率
3794	6565	57.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言