Problem

You are given a string s and an integer k.

In one operation, you can replace the character at any position with the next or previous letter in the alphabet (wrapping around so that 'a' is after 'z'). For example, replacing 'a' with the next letter results in 'b', and replacing 'a' with the previous letter results in 'z'. Similarly, replacing 'z' with the next letter results in 'a', and replacing 'z' with the previous letter results in 'y'.

Return the length of the longest palindromic subsequence of s that can be obtained after performing at most k operations.

Example 1

1
2
3
4
5
6

Input: s = "abced", k = 2
Output: 3
Explanation:
* Replace `s[1]` with the next letter, and `s` becomes `"acced"`.
* Replace `s[4]` with the previous letter, and `s` becomes `"accec"`.
The subsequence `"ccc"` forms a palindrome of length 3, which is the maximum.

Example 2

1
2
3
4
5
6
7

Input: s = "aaazzz", k = 4
Output: 6
Explanation:
* Replace `s[0]` with the previous letter, and `s` becomes `"zaazzz"`.
* Replace `s[4]` with the next letter, and `s` becomes `"zaazaz"`.
* Replace `s[3]` with the next letter, and `s` becomes `"zaaaaz"`.
The entire string forms a palindrome of length 6.

Constraints

  • 1 <= s.length <= 200
  • 1 <= k <= 200
  • s consists of only lowercase English letters.

Examples

Solution

Method 1 – Dynamic Programming with State (1)

Intuition

We use dynamic programming to find the longest palindromic subsequence, allowing up to k character changes. For each substring, we track the number of operations used and maximize the palindrome length.

Approach

  1. Define dp[l][r][op] as the length of the longest palindromic subsequence in s[l..r] using at most op operations.
  2. For each substring, if s[l] == s[r], extend the palindrome by 2.
  3. If not equal, we can use an operation (if allowed) to make them equal and extend by 2, or skip one end.
  4. Use memoization to avoid recomputation.
  5. The answer is the maximum value for dp[0][n-1][op] for op in 0..k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int longestPalindromeSubseq(string s, int k) {
        int n = s.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k+1, -1)));
        function<int(int,int,int)> dfs = [&](int l, int r, int op) -> int {
            if (l > r) return 0;
            if (l == r) return 1;
            if (dp[l][r][op] != -1) return dp[l][r][op];
            int res = max(dfs(l+1, r, op), dfs(l, r-1, op));
            if (s[l] == s[r]) res = max(res, dfs(l+1, r-1, op) + 2);
            else if (op > 0) res = max(res, dfs(l+1, r-1, op-1) + 2);
            return dp[l][r][op] = res;
        };
        return dfs(0, n-1, k);
    }
};
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def longestPalindromeSubseq(self, s: str, k: int) -> int:
        from functools import lru_cache
        n = len(s)
        @lru_cache(maxsize=None)
        def dp(l: int, r: int, op: int) -> int:
            if l > r:
                return 0
            if l == r:
                return 1
            res = max(dp(l+1, r, op), dp(l, r-1, op))
            if s[l] == s[r]:
                res = max(res, dp(l+1, r-1, op) + 2)
            elif op > 0:
                res = max(res, dp(l+1, r-1, op-1) + 2)
            return res
        return dp(0, n-1, k)
1

// Omitted for brevity. See Python for main logic.

1

// Omitted for brevity. See Python for main logic.

Complexity

  • ⏰ Time complexity: O(n^2 * k), where n is the length of s. Each state is computed once.
  • 🧺 Space complexity: O(n^2 * k), for the memoization table.