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 <= 250s 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
| class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@cache
def dfs(i, j, x):
if i >= j:
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
|
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
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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);
}
};
|
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
| 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)
}
|
