1771-由子序列构造的最长回文串的长度

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：

从 word1 中选出某个非空子序列 subsequence1 。
从 word2 中选出某个非空子序列 subsequence2 。
连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

返回可按上述方法构造的最长 回文串 的长度。如果无法构造回文串，返回 0 。

字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

示例 1：

**输入：** word1 = "cacb", word2 = "cbba"
**输出：** 5
**解释：** 从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。

示例 2：

**输入：** word1 = "ab", word2 = "ab"
**输出：** 3
**解释：** 从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。

示例 3：

**输入：** word1 = "aa", word2 = "bb"
**输出：** 0
**解释：** 无法按题面所述方法构造回文串，所以返回 0 。

提示：

1 <= word1.length, word2.length <= 1000
word1 和 word2 由小写英文字母组成

视频讲解

区间 DP【基础算法精讲 22】，制作不易，欢迎点赞！

APP 用户需要分享到微信打开链接。

第一个错误的做法

记 s = \textit{word}_1 +\textit{word}_2。看上去求出 s 的 516. 最长回文子序列就行。但不幸的是，题目要求从 word}_1 和 word}_2 中选出的子序列不能为空。例如 word}_1 = \texttt{a},\textit{word}_2 = \texttt{abcb，那么对 s=\texttt{aabcb 求最长回文子序列，得到的是 bcb，但这题要求的是 aa。

第二个错误的做法

怎么办？假设根据 516 的题解中的代码把所有的 f[i][j] 都求出来了，看上去遍历满足 i < n_1（这里 n_1 为 word}_1 的长度）和 j\ge n_1 的 i 和 j，求出 f[i][j] 的最大值就行，但是 f[i][j] 对应的子序列可能仍然在 word}_1 或 word}_2 中。

正确做法

当 s[i]=s[j] 时，算出的 f[i][j] 一定包含 s[i] 和 s[j]，所以应当在此处更新答案。

[sol2-Python3]class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        ans, n = 0, len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            f[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                    if i < len(word1) <= j:
                        ans = max(ans, f[i][j])  # f[i][j] 一定包含 s[i] 和 s[j]
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return ans

[sol2-Java]class Solution {
    public int longestPalindrome(String word1, String word2) {
        char[] s = (word1 + word2).toCharArray();
        int ans = 0, n = s.length;
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                    if (i < word1.length() && j >= word1.length()) {
                        ans = Math.max(ans, f[i][j]); // f[i][j] 一定包含 s[i] 和 s[j]
                    }
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return ans;
    }
}

[sol2-C++]class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        auto s = word1 + word2;
        int ans = 0, n = s.length(), f[n][n];
        memset(f, 0, sizeof(f));
        for (int i = n - 1; i >= 0; --i) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                    if (i < word1.length() && j >= word1.length()) {
                        ans = max(ans, f[i][j]); // f[i][j] 一定包含 s[i] 和 s[j]
                    }
                } else {
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return ans;
    }
};

[sol2-Go]func longestPalindrome(word1, word2 string) (ans int) {
    s := word1 + word2
    n := len(s)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i-- {
        f[i][i] = 1
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                f[i][j] = f[i+1][j-1] + 2
                if i < len(word1) && j >= len(word1) {
                    ans = max(ans, f[i][j]) // f[i][j] 一定包含 s[i] 和 s[j]
                }
            } else {
                f[i][j] = max(f[i+1][j], f[i][j-1])
            }
        }
    }
    return
}

func max(a, b int) int { if a < b { return b }; return a }

复杂度分析

时间复杂度：\mathcal{O}((n+m)^2)，其中 n 为 word}_1 的长度，m 为 word}_2 的长度。
空间复杂度：\mathcal{O}((n+m)^2)。