3472. 至多 K 次操作后的最长回文子序列
题目描述
给你一个字符串 s 和一个整数 k。
在一次操作中，你可以将任意位置的字符替换为字母表中相邻的字符（字母表是循环的，因此 'z' 的下一个字母是 'a'）。例如，将 'a' 替换为下一个字母结果是 'b'，将 'a' 替换为上一个字母结果是 'z'；同样，将 'z' 替换为下一个字母结果是 'a'，替换为上一个字母结果是 'y'。
返回在进行 最多 k 次操作后，s 的 最长回文子序列 的长度。
子序列 是一个 非空 字符串，可以通过删除原字符串中的某些字符（或不删除任何字符）并保持剩余字符的相对顺序得到。
回文 是正着读和反着读都相同的字符串。
示例 1：
输入: s = "abced", k = 2
输出: 3
解释:
- 将
s[1]替换为下一个字母，得到"acced"。 - 将
s[4]替换为上一个字母，得到"accec"。
子序列 "ccc" 形成一个长度为 3 的回文，这是最长的回文子序列。
示例 2：
输入: s = "aaazzz", k = 4
输出: 6
解释:
- 将
s[0]替换为上一个字母，得到"zaazzz"。 - 将
s[4]替换为下一个字母，得到"zaazaz"。 - 将
s[3]替换为下一个字母，得到"zaaaaz"。
整个字符串形成一个长度为 6 的回文。
提示:
1 <= s.length <= 2001 <= k <= 200s仅由小写英文字母组成。
解法
方法一：记忆化搜索
我们设计一个函数 $\textit{dfs}(i, j, k)$，表示在字符串 $s[i..j]$ 中最多可以进行 $k$ 次操作，得到的最长回文子序列的长度。那么答案为 $\textit{dfs}(0, n - 1, k)$。
函数 $\textit{dfs}(i, j, k)$ 的计算过程如下：
如果 $i > j$，返回 $0$；
如果 $i = j$，返回 $1$；
否则，我们可以忽略 $s[i]$ 或 $s[j]$，分别计算 $\textit{dfs}(i + 1, j, k)$ 和 $\textit{dfs}(i, j - 1, k)$；或者我们可以将 $s[i]$ 和 $s[j]$ 变成相同的字符，计算 $\textit{dfs}(i + 1, j - 1, k - t) + 2$，其中 $t$ 是 $s[i]$ 和 $s[j]$ 的 ASCII 码差值。
返回上述三种情况的最大值。
为了避免重复计算，我们使用记忆化搜索的方法。
时间复杂度 $O(n^2 \times k)$，空间复杂度 $O(n^2 \times k)$。其中 $n$ 是字符串 $s$ 的长度。
Python3
class Solution:
def longestPalindromicSubsequence(self, s: str, k: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i > j:
return 0
if i == j:
return 1
res = max(dfs(i + 1, j, k), dfs(i, j - 1, k))
d = abs(s[i] - s[j])
t = min(d, 26 - d)
if t <= k:
res = max(res, dfs(i + 1, j - 1, k - t) + 2)
return res
s = list(map(ord, s))
n = len(s)
ans = dfs(0, n - 1, k)
dfs.cache_clear()
return ans
Java
class Solution {
private char[] s;
private Integer[][][] f;
public int longestPalindromicSubsequence(String s, int k) {
this.s = s.toCharArray();
int n = s.length();
f = new Integer[n][n][k + 1];
return dfs(0, n - 1, k);
}
private int dfs(int i, int j, int k) {
if (i > j) {
return 0;
}
if (i == j) {
return 1;
}
if (f[i][j][k] != null) {
return f[i][j][k];
}
int res = Math.max(dfs(i + 1, j, k), dfs(i, j - 1, k));
int d = Math.abs(s[i] - s[j]);
int t = Math.min(d, 26 - d);
if (t <= k) {
res = Math.max(res, 2 + dfs(i + 1, j - 1, k - t));
}
f[i][j][k] = res;
return res;
}
}
C++
class Solution {
public:
int longestPalindromicSubsequence(string s, int k) {
int n = s.size();
vector f(n, vector(n, vector<int>(k + 1, -1)));
auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
if (i > j) {
return 0;
}
if (i == j) {
return 1;
}
if (f[i][j][k] != -1) {
return f[i][j][k];
}
int res = max(dfs(i + 1, j, k), dfs(i, j - 1, k));
int d = abs(s[i] - s[j]);
int t = min(d, 26 - d);
if (t <= k) {
res = max(res, 2 + dfs(i + 1, j - 1, k - t));
}
return f[i][j][k] = res;
};
return dfs(0, n - 1, k);
}
};
Go
func longestPalindromicSubsequence(s string, k int) 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, k+1)
for l := range f[i][j] {
f[i][j][l] = -1
}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) int {
if i > j {
return 0
}
if i == j {
return 1
}
if f[i][j][k] != -1 {
return f[i][j][k]
}
res := max(dfs(i+1, j, k), dfs(i, j-1, k))
d := abs(int(s[i]) - int(s[j]))
t := min(d, 26-d)
if t <= k {
res = max(res, 2+dfs(i+1, j-1, k-t))
}
f[i][j][k] = res
return res
}
return dfs(0, n-1, k)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
TypeScript
function longestPalindromicSubsequence(s: string, k: number): number {
const n = s.length;
const sCodes = s.split('').map(c => c.charCodeAt(0));
const f: number[][][] = Array.from({ length: n }, () =>
Array.from({ length: n }, () => Array(k + 1).fill(-1)),
);
function dfs(i: number, j: number, k: number): number {
if (i > j) {
return 0;
}
if (i === j) {
return 1;
}
if (f[i][j][k] !== -1) {
return f[i][j][k];
}
let res = Math.max(dfs(i + 1, j, k), dfs(i, j - 1, k));
const d = Math.abs(sCodes[i] - sCodes[j]);
const t = Math.min(d, 26 - d);
if (t <= k) {
res = Math.max(res, 2 + dfs(i + 1, j - 1, k - t));
}
return (f[i][j][k] = res);
}
return dfs(0, n - 1, k);
}