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