2025-09-04：至多 K 次操作后的最长回文子序列。用go语言，给定一个字符串 s 和一个整数 k。你可以最多进行 k 次

2025-09-04：至多 K 次操作后的最长回文子序列。用go语言，给定一个字符串 s 和一个整数 k。你可以最多进行 k 次单步修改：每次选定字符串中的某个字符，将它变成字母表中与之相邻的字母——字母表按环状处理（例如对 z 向前一步得到 y，向后一步得到 a；对 a 向前一步得到 z，向后一步得到 b）。同一个位置可以多次修改，但所有修改的总次数不能超过 k。

在最多 k 次这样的修改之后，考察修改后字符串的最长回文子序列（子序列指通过删除若干字符并保持原有相对次序得到的非空串；回文指正反读相同）。要求返回能够达到的最长回文子序列的最大长度。

1 <= s.length <= 200。

1 <= k <= 200。

s 仅由小写英文字母组成。

输入: s = "abced", k = 2。

输出: 3。

解释:

将 s[1] 替换为下一个字母，得到 "acced"。

将 s[4] 替换为上一个字母，得到 "accec"。

子序列 "ccc" 形成一个长度为 3 的回文，这是最长的回文子序列。

题目来自力扣3472。

解决思路

1. 1. 问题转换： 我们实际上允许对原字符串进行最多 k 次修改（每次修改一个字符，可以多次修改同一位置），然后求新字符串的最长回文子序列。注意，修改操作可以在任意位置进行任意次数（总次数不超过 k），且每次修改只能变成相邻字符（环状字母表）。
2. 2. 关键观察：
   • • 最长回文子序列（LPS）不一定需要连续，但可以通过删除字符得到。
   • • 修改操作可以帮助我们使一些原本不相同的字符对变得相同（从而可以成为回文的一部分），但需要消耗操作次数。
   • • 对于一对对称位置的字符（比如 s[i] 和 s[j]），如果它们不相同，我们可以通过修改操作使它们相同。修改的最小操作次数为 min(|s[i]-s[j]|, 26-|s[i]-s[j]|)（因为字母表是环状的）。
3. 3. 动态规划（DP）设置： 我们使用一个三维DP数组 f[k][i][j] 表示在最多使用 k 次操作的情况下，子串 s[i:j+1] 中能获得的最长回文子序列长度。
4. 4. DP状态转移：
   • • 基础情况：当 i == j 时，只有一个字符，回文长度为1。
   • • 对于区间 [i, j]：
     • • 如果不使用 s[i] 和 s[j]，那么最大长度为 max(f[k][i+1][j], f[k][i][j-1])。
     • • 如果使用 s[i] 和 s[j] 作为回文的两端，那么需要将它们修改为相同字符。设修改所需操作次数为 op = min(|s[i]-s[j]|, 26-|s[i]-s[j]|)。如果 op <= k，那么我们可以用 k - op 次操作来处理内部子串 [i+1, j-1]，即 f[k-op][i+1][j-1] + 2。
   • • 取上述情况的最大值。
5. 5. 初始化与计算顺序：
   • • 初始化：对于所有 k（0到K）和所有 i，f[k][i][i] = 1。
   • • 计算顺序：从短区间到长区间（即 j-i 从小到大），同时对于每个区间，遍历操作次数 k（从0到K）。
6. 6. 最终答案： 整个字符串在最多使用 k 次操作后的最长回文子序列长度为 f[K][0][n-1]。

详细步骤（以示例 s = "abced", k=2 为例）：

1. 1. 字符串长度为5，初始字符：'a','b','c','e','d'。
2. 2. 首先，检查整个字符串是否可以通过不超过 k 次操作变成完全回文？即计算所有对称位置（(0,4), (1,3)）的操作次数和：
   • • (0,4): 'a'和'd'的差值 |'a'-'d'| = 3，环状最小操作次数为 min(3,23)=3。
   • • (1,3): 'b'和'e'的差值 |'b'-'e'| = 3，min(3,23)=3。 总操作次数至少需要3+3=6>2，所以不能整个变成回文。
3. 3. 使用DP计算：
   • • 考虑区间[0,4]：
     • • 如果不使用两端：最大为 max(f[2][1][4], f[2][0][3])。
     • • 如果使用两端：操作次数op=3（将'a'和'd'变成相同），但3>2（当前k=2），所以不能使用。
   • • 因此需要继续分解子问题。
4. 4. 最终找到最长回文子序列为"ccc"（长度3），通过修改： - 将s[1]（原为'b'）改为'c'（操作1次：向后一步）。 - 将s[4]（原为'd'）改为'c'（操作1次：向前一步）。 总操作次数为2，满足条件。

时间复杂度和空间复杂度

• • 时间复杂度： DP状态有三维：操作次数 k（0到K），左端点 i（0到n-1），右端点 j（0到n-1）。因此状态总数为 O(K * n^2)。每个状态的计算需要常数时间（比较几个情况）。所以总时间复杂度为 O(K * n^2)。
• • 空间复杂度： 需要存储三维DP数组，大小为 (K+1) * n * n，因此空间复杂度为 O(K * n^2)。

对于约束（n<=200, k<=200），状态数约为200200200=8e6，在Go语言中是可以接受的。

总结

该方法通过动态规划巧妙地结合了修改操作和最长回文子序列问题，利用三维状态来记录操作次数和区间信息，逐步推导出最优解。计算顺序从小区间到大区间，确保子问题先被求解。最终答案即整个字符串在最多k次操作后的最长回文子序列长度。

Go完整代码如下：

.

package main

import (
    "fmt"
)

func longestPalindromicSubsequence(s string, K int)int {
    n := len(s)
    cnt := 0
    for i := range n / 2 {
        d := abs(int(s[i]) - int(s[n-1-i]))
        cnt += min(d, 26-d)
    }
    if cnt <= K {
        return n
    }

    f := make([][][]int, K+1)
    for k := range f {
        f[k] = make([][]int, n)
        for i := n - 1; i >= 0; i-- {
            f[k][i] = make([]int, n)
            f[k][i][i] = 1
            for j := i + 1; j < n; j++ {
                res := max(f[k][i+1][j], f[k][i][j-1])
                d := abs(int(s[i]) - int(s[j]))
                op := min(d, 26-d)
                if op <= k {
                    res = max(res, f[k-op][i+1][j-1]+2)
                }
                f[k][i][j] = res
            }
        }
    }
    return f[K][0][n-1]
}

func abs(x int)int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    s := "abced"
    k := 2
    result := longestPalindromicSubsequence(s, k)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def longestPalindromicSubsequence(s: str, K: int) -> int:
    n = len(s)
    cnt = 0
    for i in range(n // 2):
        d = abs(ord(s[i]) - ord(s[n - 1 - i]))
        cnt += min(d, 26 - d)
    if cnt <= K:
        return n

    # 初始化三维DP数组
    f = [[[0] * n for _ in range(n)] for _ in range(K + 1)]
    
    for k in range(K + 1):
        for i in range(n - 1, -1, -1):
            f[k][i][i] = 1
            for j in range(i + 1, n):
                res = max(f[k][i + 1][j], f[k][i][j - 1])
                d = abs(ord(s[i]) - ord(s[j]))
                op = min(d, 26 - d)
                if op <= k:
                    res = max(res, f[k - op][i + 1][j - 1] + 2)
                f[k][i][j] = res
    
    return f[K][0][n - 1]

def main():
    s = "abced"
    k = 2
    result = longestPalindromicSubsequence(s, k)
    print(result)

if __name__ == "__main__":
    main()

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，让AI助力您的未来发展。