Formatted question description: https://leetcode.ca/all/1682.html

Level

Medium

Description

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.

Solution

Use dynamic programming. Let n be the length of s. Create a 3D array dp of size n * n * 26, where dp[i][j][k] represents the length of the longest palindromic subsequence from index i to index j where the outmost letter is the k-th letter (0-indexed). For each pair of (i, j) where i < j, loop over k. Let c be the k-th letter. If s.charAt(i) != c, then dp[i][j][k] = dp[i + 1][j][k]. If s.charAt(j) != c, then dp[i][j][k] = dp[i][j - 1][k]. Otherwise, loop over m from 0 to 25 and calculate the maximum previous length as prevLength = max{dp[i + 1][j - 1][m]} among the values of m where m != k. Then dp[i][j][k] = prevLength + 2.

After the values of dp are calculated, loop over k from 0 to 25 to obtain the maximum among dp[0][n - 1][k]. Finally, return the maximum.

Code

Java

class Solution {
    public int longestPalindromeSubseq(String s) {
        int length = s.length();
        int[][][] dp = new int[length][length][26];
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                for (int k = 0; k < 26; k++) {
                    char c = (char) ('a' + k);
                    if (s.charAt(i) != c)
                        dp[i][j][k] = dp[i + 1][j][k];
                    else if (s.charAt(j) != c)
                        dp[i][j][k] = dp[i][j - 1][k];
                    else {
                        int prevLength = 0;
                        for (int m = 0; m < 26; m++) {
                            if (m != k) // here is to satisfy 'No two consecutive characters are equal, except the two middle ones.'
                                prevLength = Math.max(prevLength, dp[i + 1][j - 1][m]);
                        }
                        dp[i][j][k] = prevLength + 2;
                    }
                }
            }
        }
        int maxLength = 0;
        for (int k = 0; k < 26; k++)
            maxLength = Math.max(maxLength, dp[0][length - 1][k]);
        return maxLength;
    }
}

All Problems

All Solutions