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

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[n - 1][k]. Finally, return the maximum.

Java