1682. Longest Palindromic Subsequence II π
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.
Solutions
Solution 1: Memorization Search
We design a function $dfs(i, j, x)$ to represent the length of the longest "good" palindrome subsequence ending with character $x$ in the index range $[i, j]$ of string $s$. The answer is $dfs(0, n - 1, 26)$.
The calculation process of the function $dfs(i, j, x)$ is as follows:
- If $i >= j$, then $dfs(i, j, x) = 0$;
- If $s[i] = s[j]$ and $s[i] \neq x$, then $dfs(i, j, x) = dfs(i + 1, j - 1, s[i]) + 2$;
- If $s[i] \neq s[j]$, then $dfs(i, j, x) = max(dfs(i + 1, j, x), dfs(i, j - 1, x))$.
During the process, we can use memorization search to avoid repeated calculations.
The time complexity is $O(n^2 \times C)$. Where $n$ is the length of the string $s$, and $C$ is the size of the character set. In this problem, $C = 26$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |