1682. Longest Palindromic Subsequence II

09/20/2021

Leetcode

A subsequence of a string s is considered a good palindromic subsequence if:

• It is a subsequence of s.

• It is a palindrome (has the same value if reversed).

• It has an even length.

• No two consecutive characters are equal, except the two middle ones.

For example, if s = "abcabcabb", then "abba" is considered a good palindromic subsequence, while "bcb" (not even length) and "bbbb" (has equal consecutive characters) are not.

Given a string s, return the length of the longest good palindromic subsequence in s.

Example 1:

Input: s = "bbabab"
Output: 4
Explanation: The longest good palindromic subsequence of s is "baab".

Example 2:

Input: s = "dcbccacdb"
Output: 4
Explanation: The longest good palindromic subsequence of s is "dccd".

Constraints:

• 1 <= s.length <= 250

• s consists of lowercase English letters.

Basic Idea

这道题和最长回文子序列问题很像，even number元素也很容易处理，唯独相邻的字母不能相等比较复杂。我们可以类似的使用一个三维数组进行DP，增加一个纬度用来存前一个（外面一层）相邻的字母。

代码可以仍使用Top down dfs来写，需要注意的是当准备选择当前一对相同字母的时候要检查它们是否和外层的prev相同，如果项同则必须跳过。

一定要注意cache要用Integer[][][] 因为使用int数组我们就不知道0是故意set到0还是没有set过。

Java Code：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int N = s.length();
        // 注意这里一定要用Integer，否则无法区分0值是cache过的值还是未曾算过这里
        Integer[][][] dp = new Integer[N][N][256];
        int ret = dfs(dp, s, 0, N - 1, 255);
        return ret;
    }
    
    private int dfs(Integer[][][] dp, String s, int left, int right, int prev) {
        if (left >= right) return 0; // 长度必须为even，所以中间不能为单个字母
        if (dp[left][right][prev] != null) return dp[left][right][prev];
        if (s.charAt(left) == s.charAt(right) && s.charAt(left) != prev) {
            dp[left][right][prev] = 2 + dfs(dp, s, left + 1, right - 1, s.charAt(left));
        } else {
            // 跳过当前left和right的时候，需要将prev传下去
            dp[left][right][prev] 
                = Math.max(dfs(dp, s, left + 1, right, prev), dfs(dp, s, left, right - 1, prev));
        }
        return dp[left][right][prev];
    }
}