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 {
public:
    int f[251][251][27];

    int longestPalindromeSubseq(string s) {
        int n = s.size();
        memset(f, -1, sizeof f);
        function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {
            if (i >= j) return 0;
            if (f[i][j][x] != -1) return f[i][j][x];
            int ans = 0;
            if (s[i] == s[j] && s[i] - 'a' != x)
                ans = dfs(i + 1, j - 1, s[i] - 'a') + 2;
            else
                ans = max(dfs(i + 1, j, x), dfs(i, j - 1, x));
            f[i][j][x] = ans;
            return ans;
        };
        return dfs(0, n - 1, 26);
    }
};