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.
Rust Solution
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);
}
Having problems with this solution? Click here to submit an issue on github.