Medium
题目描述
给你一个字符串 s 和一个整数 k。
在一次操作中，你可以将任意位置的字符替换为字母表中的下一个或前一个字母（循环包装，所以 ‘a’ 的下一个是 ‘z’）。例如，将 ‘a’ 替换为下一个字母得到 ‘b’，将 ‘a’ 替换为前一个字母得到 ‘z’。同样，将 ‘z’ 替换为下一个字母得到 ‘a’，将 ‘z’ 替换为前一个字母得到 ‘y’。
返回执行最多 k 次操作后，可以获得的 s 的最长回文子序列的长度。
示例 1：
输入：s = "abced", k = 2
输出：3
解释：
将 s[1] 替换为下一个字母，s 变成 "acced"。
将 s[4] 替换为前一个字母，s 变成 "accec"。
子序列 "ccc" 形成长度为 3 的回文，这是最大值。
示例 2：
输入：s = "aaazzz", k = 4
输出：6
解释：
将 s[0] 替换为前一个字母，s 变成 "zaazzz"。
将 s[4] 替换为下一个字母，s 变成 "zaazaz"。
将 s[3] 替换为下一个字母，s 变成 "zaaaaz"。
整个字符串形成长度为 6 的回文。
约束条件：
1 <= s.length <= 2001 <= k <= 200s仅由小写英文字母组成
解题思路
这是一道经典的区间动态规划问题，需要考虑字符替换的成本。
核心思路：
定义 dp[i][j][cost] 表示在子串 s[i..j] 中，使用最多 cost 次操作能获得的最长回文子序列长度。
状态转移：
对于每个区间
[i, j]，有三种选择：- 不选择
s[i]：dp[i+1][j][cost] - 不选择
s[j]：dp[i][j-1][cost] - 同时选择
s[i]和s[j]：需要计算将它们变成相同字符的最小代价
- 不选择
关键计算 - 字符间距离： 对于两个字符
a和b，在环形字母表中的最小距离为：min(abs(a-b), 26-abs(a-b))优化技巧： 当选择
s[i]和s[j]时，我们枚举26个字母，找到使总代价最小且不超过cost的目标字符。
时间复杂度优化： 通过预计算字符间的最小距离，避免重复计算。状态转移时，对每个可能的目标字符进行尝试，选择代价最小的方案。
这种方法能够在 O(n³×k×26) 的时间复杂度内解决问题，对于给定的约束条件是可接受的。
代码实现
class Solution {
public:
int longestPalindromicSubsequence(string s, int k) {
int n = s.length();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, 0)));
// Base case: single characters
for (int i = 0; i < n; i++) {
for (int cost = 0; cost <= k; cost++) {
dp[i][i][cost] = 1;
}
}
// Fill dp table
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
for (int cost = 0; cost <= k; cost++) {
// Option 1: don't include s[i]
dp[i][j][cost] = dp[i + 1][j][cost];
// Option 2: don't include s[j]
dp[i][j][cost] = max(dp[i][j][cost], dp[i][j - 1][cost]);
// Option 3: include both s[i] and s[j]
if (i + 1 <= j - 1) {
for (char target = 'a'; target <= 'z'; target++) {
int cost1 = min(abs(s[i] - target), 26 - abs(s[i] - target));
int cost2 = min(abs(s[j] - target), 26 - abs(s[j] - target));
int totalCost = cost1 + cost2;
if (totalCost <= cost) {
dp[i][j][cost] = max(dp[i][j][cost],
dp[i + 1][j - 1][cost - totalCost] + 2);
}
}
} else {
// Adjacent characters
for (char target = 'a'; target <= 'z'; target++) {
int cost1 = min(abs(s[i] - target), 26 - abs(s[i] - target));
int cost2 = min(abs(s[j] - target), 26 - abs(s[j] - target));
int totalCost = cost1 + cost2;
if (totalCost <= cost) {
dp[i][j][cost] = max(dp[i][j][cost], 2);
}
}
}
}
}
}
return dp[0][n - 1][k];
}
};
class Solution:
def longestPalindromicSubsequence(self, s: str, k: int) -> int:
n = len(s)
dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]
# Base case: single characters
for i in range(n):
for cost in range(k + 1):
dp[i][i][cost] = 1
# Fill dp table
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for cost in range(k + 1):
# Option 1: don't include s[i]
dp[i][j][cost] = dp[i + 1][j][cost]
# Option 2: don't include s[j]
dp[i][j][cost] = max(dp[i][j][cost], dp[i][j - 1][cost])
# Option 3: include both s[i] and s[j]
for target in range(26):
target_char = chr(ord('a') + target)
cost1 = min(abs(ord(s[i]) - ord(target_char)),
26 - abs(ord(s[i]) - ord(target_char)))
cost2 = min(abs(ord(s[j]) - ord(target_char)),
26 - abs(ord(s[j]) - ord(target_char)))
total_cost = cost1 + cost2
if total_cost <= cost:
if i + 1 <= j - 1:
dp[i][j][cost] = max(dp[i][j][cost],
dp[i + 1][j - 1][cost - total_cost] + 2)
else:
dp[i][j][cost] = max(dp[i][j][cost], 2)
return dp[0][n - 1][k]
public class Solution {
public int LongestPalindromicSubsequence(string s, int k) {
int n = s.Length;
int[,,] dp = new int[n, n, k + 1];
// Base case: single characters
for (int i = 0; i < n; i++) {
for (int cost = 0; cost <= k; cost++) {
dp[i, i, cost] = 1;
}
}
// Fill dp table
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
for (int cost = 0; cost <= k; cost++) {
// Option 1: don't include s[i]
dp[i, j, cost] = dp[i + 1, j, cost];
// Option 2: don't include s[j]
dp[i, j, cost] = Math.Max(dp[i, j, cost], dp[i, j - 1, cost]);
// Option 3: include both s[i] and s[j]
for (char target = 'a'; target <= 'z'; target++) {
int cost1 = Math.Min(Math.Abs(s[i] - target), 26 - Math.Abs(s[i] - target));
int cost2 = Math.Min(Math.Abs(s[j] - target), 26 - Math.Abs(s[j] - target));
int totalCost = cost1 + cost2;
if (totalCost <= cost) {
if (i + 1 <= j - 1) {
dp[i, j, cost] = Math.Max(dp[i, j, cost],
dp[i + 1, j - 1, cost - totalCost] + 2);
} else {
dp[i, j, cost] = Math.Max(dp[i, j, cost], 2);
}
}
}
}
}
}
return dp[0, n - 1, k];
}
}
var longestPalindromicSubsequence = function(s, k) {
const n = s.length;
const dp = Array(n).fill(null).map(() =>
Array(n).fill(null).map(() => Array(k + 1).fill(0))
);
// Base case: single characters
for (let i = 0; i < n; i++) {
for (let cost = 0; cost <= k; cost++) {
dp[i][i][cost] = 1;
}
}
// Fill dp table
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
for (let cost = 0; cost <= k; cost++) {
// Option 1: don't include s[i]
dp[i][j][cost] = dp[i + 1][j][cost];
// Option 2: don't include s[j]
dp[i][j][cost] = Math.max(dp[i][j][cost], dp[i][j - 1][cost]);
// Option 3: include both s[i] and s[j]
for (let targetCode = 0; targetCode < 26; targetCode++) {
const target = String.fromCharCode(97 + targetCode); // 'a' + targetCode
const cost1 = Math.min(Math.abs(s.charCodeAt(i) - target.charCodeAt(0)),
26 - Math.abs(s.charCodeAt(i) - target.charCodeAt(0)));
const cost2 = Math.min(Math.abs(s.charCodeAt(j) - target.charCodeAt(0)),
26 - Math.abs(s.charCodeAt(j) - target.charCodeAt(0)));
const totalCost = cost1 + cost2;
if (totalCost <= cost) {
if (i + 1 <= j - 1) {
dp[i][j][cost] = Math.max(dp[i][j][cost],
dp[i + 1][j - 1][cost - totalCost] + 2);
} else {
dp[i][j][cost] = Math.max(dp[i][j][cost], 2);
}
}
}
}
}
}
return dp[0][n - 1][k];
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n³ × k × 26) | n为字符串长度，需要遍历所有区间、所有成本值和所有可能的目标字符 |
| 空间复杂度 | O(n² × k) | 三维DP数组的空间开销 |