1682. Longest Palindromic Subsequence II

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.

class Solution {
    int dp[251][251][256];
    int helper(string& s, int l, int r, char last) {
        if(l >= r) return 0;
        int& res = dp[l][r][last];
        if(res != -1) return res;
        if(s[l] == s[r] and last != s[l])
            res = max(helper(s,l+1,r-1,s[l]) + 2, helper(s,l+1,r-1,last));
        if(s[l] == s[r] and last == s[l])
            res = helper(s,l+1,r-1,last);
        if(s[l] != s[r])
            res = max(helper(s,l+1,r,last), helper(s,l,r-1,last));
        
        return res;
    }
public:
    int longestPalindromeSubseq(string s) {
        memset(dp,-1,sizeof(dp));
        return helper(s,0,s.length() -1, '#');
    }
};