跳转至

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 <= 200
  • 1 <= k <= 200
  • s 仅由小写英文字母组成。

解法

方法一：记忆化搜索

我们设计一个函数 \(\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\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

 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
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;
    }
}

 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
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);
    }
};

 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
34
35
36
37
38
39
40
41
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
}

 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
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);
}

评论