What is the main approach to solve the "Longest Palindromic Subsequence After at Most K Operations"?

The problem can be solved using dynamic programming with a focus on state transitions, where the state represents the longest palindromic subsequence possible with a limited number of character modifications.

How do the k operations affect the palindrome formation?

The k operations allow you to modify characters in the string, either by advancing or retreating alphabetically. These operations are crucial for creating a longer palindromic subsequence by adjusting mismatched characters.

What is the time complexity of solving the "Longest Palindromic Subsequence After at Most K Operations"?

The time complexity is O(n^2 * k), where n is the length of the string and k is the number of operations, assuming a dynamic programming solution is used.

How can we optimize the solution for larger inputs?

Optimizing space complexity and focusing on efficient state transitions can help improve the solution for larger inputs. Avoiding redundant calculations and minimizing the size of the DP table are key strategies.

What are some common mistakes in solving this problem?

Common mistakes include failing to handle the alphabet wrapping correctly, neglecting to track changes efficiently, and not optimizing space or time complexity in the dynamic programming approach.

#3472

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

至多 K 次操作后的最长回文子序列

给你一个字符串 s 和一个整数 k 。在一次操作中，你可以将任意位置的字符替换为字母表中相邻的字符（字母表是循环的，因此 'z' 的下一个字母是 'a' ）。例如，将 'a' 替换为下一个字母结果是 'b' ，将 'a' 替换为上一个字母结果是 'z' ；同样，将 'z' 替换为下一个字母结果是 …

字符串动态规划

题目描述

给你一个字符串 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 仅由小写英文字母组成。

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $\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

21

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

speed

复杂度分析

指标	值
时间	and space complexity depend on the approach used for the dynamic programming table. A straightforward implementation would have a time complexity of O(n^2 * k), where n is the string length and k is the number of operations. The space complexity is O(n^2), as the DP table requires storage for all substrings of s.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of state transition dynamic programming in string manipulation problems.
question_mark
Evaluate how efficiently they handle the complexity of operations and character adjustments.
question_mark
Assess the candidate's ability to optimize the solution, particularly in handling the k operations efficiently.

warning

常见陷阱

外企场景

error
Failing to consider the wrapping alphabet when calculating character adjustments.
error
Overcomplicating the problem by ignoring the efficiency of the dynamic programming approach.
error
Neglecting to optimize space usage, especially when dealing with large strings and many operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider limiting the number of changes even further (e.g., at most 1 operation).
arrow_right_alt
Extend the problem to allow additional string manipulations such as insertions or deletions.
arrow_right_alt
Explore the problem with a constraint that restricts certain characters from being changed.

help

常见问题

外企场景

继续练习

#3458 选择 K 个互不重叠的特殊子字符串 #3448 统计可以被最后一个数位整除的子字符串数目 #3441 变成好标题的最少代价