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`.

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.

1682. Longest Palindromic Subsequence II
``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn longest_palindrome_subseq(s: String) -> i32 {
let n = s.len();
let s: Vec<u8> = s.bytes().collect();
let mut res = 0;
let mut memo: HashMap<(usize, usize, u8), i32> = HashMap::new();
for i in 0..26 {
res = res.max(Self::dp(0, n - 1, i as u8 + b'a', &mut memo, &s));
}
res
}
fn dp(
left: usize,
right: usize,
c: u8,
memo: &mut HashMap<(usize, usize, u8), i32>,
s: &[u8],
) -> i32 {
if left >= right {
return 0;
}
if let Some(&res) = memo.get(&(left, right, c)) {
res
} else {
let mut l = left;
while l < right && s[l] != c {
l += 1;
}
let mut r = right;
while r > l && s[r] != c {
r -= 1;
}
let res = if l == r {
0
} else {
let mut res = 0;
for i in 0..26 {
let d = b'a' + i as u8;
if d != c {
res = res.max(2 + Self::dp(l + 1, r - 1, d, memo, s));
}
}
res
};
memo.insert((left, right, c), res);
res
}
}
}

#[test]
fn test() {
let s = "bbabab".to_string();
let res = 4;
assert_eq!(Solution::longest_palindrome_subseq(s), res);
let s = "dcbccacdb".to_string();
let res = 4;
assert_eq!(Solution::longest_palindrome_subseq(s), res);
let s = "boob".to_string();
let res = 4;
assert_eq!(Solution::longest_palindrome_subseq(s), res);
}
``````