Longest Palindromic Subsequence II
<p>A subsequence of a string <code>s</code> is considered a <strong>good palindromic subsequence</strong> if:</p>

<ul>
	<li>It is a subsequence of <code>s</code>.</li>
	<li>It is a palindrome (has the same value if reversed).</li>
	<li>It has an <strong>even</strong> length.</li>
	<li>No two consecutive characters are equal, except the two middle ones.</li>
</ul>

<p>For example, if <code>s = &quot;abcabcabb&quot;</code>, then <code>&quot;abba&quot;</code> is considered a <strong>good palindromic subsequence</strong>, while <code>&quot;bcb&quot;</code> (not even length) and <code>&quot;bbbb&quot;</code> (has equal consecutive characters) are not.</p>

<p>Given a string <code>s</code>, return <em>the <strong>length</strong> of the <strong>longest good palindromic subsequence</strong> in </em><code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbabab&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest good palindromic subsequence of s is &quot;baab&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dcbccacdb&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest good palindromic subsequence of s is &quot;dccd&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 250</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>
String; Dynamic Programming
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def dfs(i, j, x):
            if i >= j:
                return 0
            if s[i] == s[j] and s[i] != x:
                return dfs(i + 1, j - 1, s[i]) + 2
            return max(dfs(i + 1, j, x), dfs(i, j - 1, x))

        ans = dfs(0, len(s) - 1, '')
        dfs.cache_clear()
        return ans
