##### Welcome to Subscribe On Youtube

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

# Code

• class Solution {
public int longestPalindromeSubseq(String s) {
int length = s.length();
int[][][] dp = new int[length][length][26];
for (int i = length - 2; i >= 0; i--) {
for (int j = i + 1; j < length; j++) {
for (int k = 0; k < 26; k++) {
char c = (char) ('a' + k);
if (s.charAt(i) != c)
dp[i][j][k] = dp[i + 1][j][k];
else if (s.charAt(j) != c)
dp[i][j][k] = dp[i][j - 1][k];
else {
int prevLength = 0;
for (int m = 0; m < 26; m++) {
if (m != k) // here is to satisfy 'No two consecutive characters are equal, except the two middle ones.'
prevLength = Math.max(prevLength, dp[i + 1][j - 1][m]);
}
dp[i][j][k] = prevLength + 2;
}
}
}
}
int maxLength = 0;
for (int k = 0; k < 26; k++)
maxLength = Math.max(maxLength, dp[0][length - 1][k]);
return maxLength;
}
}

############

class Solution {
private int[][][] f;
private String s;

public int longestPalindromeSubseq(String s) {
int n = s.length();
this.s = s;
f = new int[n][n][27];
for (var a : f) {
for (var b : a) {
Arrays.fill(b, -1);
}
}
return dfs(0, n - 1, 26);
}

private int dfs(int i, int j, int x) {
if (i >= j) {
return 0;
}
if (f[i][j][x] != -1) {
return f[i][j][x];
}
int ans = 0;
if (s.charAt(i) == s.charAt(j) && s.charAt(i) - 'a' != x) {
ans = dfs(i + 1, j - 1, s.charAt(i) - 'a') + 2;
} else {
ans = Math.max(dfs(i + 1, j, x), dfs(i, j - 1, x));
}
f[i][j][x] = ans;
return ans;
}
}

• 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);
}
};

• class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
length = len(s)
dp = [[[0 for _ in range(26)] for _ in range(length)] for _ in range(length)]
for i in range(length - 2, -1, -1):
for j in range(i + 1, length):
for k in range(26):
c = chr(ord('a') + k)
if s[i] != c:
dp[i][j][k] = dp[i + 1][j][k]
elif s[j] != c:
dp[i][j][k] = dp[i][j - 1][k]
else:
prevLength = 0
for m in range(26):
if m != k:
prevLength = max(prevLength, dp[i + 1][j - 1][m])
dp[i][j][k] = prevLength + 2
maxLength = 0
for k in range(26):
maxLength = max(maxLength, dp[0][length - 1][k])
return maxLength

############

class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@cache
def dfs(i, j, x):
if i >= j: # i==j, then it's an odd one, not valid
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

• func longestPalindromeSubseq(s string) int {
n := len(s)
f := make([][][]int, n)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, 27)
for k := range f[i][j] {
f[i][j][k] = -1
}
}
}
var dfs func(i, j, x int) int
dfs = func(i, j, x int) int {
if i >= j {
return 0
}
if f[i][j][x] != -1 {
return f[i][j][x]
}
ans := 0
if s[i] == s[j] && int(s[i]-'a') != x {
ans = dfs(i+1, j-1, int(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)
}

func max(a, b int) int {
if a > b {
return a
}
return b
}