# Longest Palindromic Subsequence After at Most K Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-palindromic-subsequence-after-at-most-k-operations)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindromic-subsequence-after-at-most-k-operations
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## 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:**

**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:**

**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.

# Approaches
## 3D Dynamic Programming
This problem can be solved using dynamic programming. It's an extension of the classic Longest Palindromic Subsequence (LPS) problem. The standard LPS DP state `dp[i][j]` (length of LPS in `s[i...j]`) is insufficient because it doesn't track the cost of operations. We can incorporate the cost by adding a third dimension to our DP state: `k`. This leads to a 3D DP table, `dp[i][j][k]`, which stores the maximum length of a palindromic subsequence for `s[i...j]` using at most `k` operations.
**Time:** O(n^2 * k). We have three nested loops to fill the DP table: `i` from `n-1` to `0` (n iterations), `j` from `i+1` to `n-1` (at most n iterations), and `rem_k` from `0` to `k` (k+1 iterations). · **Space:** O(n^2 * k), where `n` is the length of the string and `k` is the maximum number of operations. This is for the 3D DP table of size `n x n x (k+1)`.
**Pros:** It's a conceptually clear extension of the standard Longest Palindromic Subsequence algorithm.; The approach is guaranteed to find the optimal solution by systematically exploring all subproblems.
**Cons:** The space complexity of `O(n^2 * k)` can be very high. For the given constraints (`n=200, k=200`), this would require approximately `200 * 200 * 201 * 4` bytes, which is about 32 MB of memory. This might be prohibitive in environments with stricter memory limits.
### Explanation
We can define a function, say `solve(i, j, k)`, that returns the length of the longest palindromic subsequence in `s[i...j]` with at most `k` operations. We can implement this using a bottom-up DP approach to avoid recursion overhead.

The state transition for `dp[i][j][rem_k]` is as follows:
- We consider the characters at the ends of our current substring, `s[i]` and `s[j]`.
- **Option 1: Don't use `s[i]`**. We find the LPS in the smaller substring `s[i+1...j]` with the same budget `rem_k`. The length is `dp[i+1][j][rem_k]`.
- **Option 2: Don't use `s[j]`**. We find the LPS in `s[i...j-1]` with budget `rem_k`. The length is `dp[i][j-1][rem_k]`.
- **Option 3: Match `s[i]` and `s[j]`**. To make them part of the palindrome, they must be transformed into the same character. The minimum cost for this is `cost(s[i], s[j]) = min(|s[i] - s[j]|, 26 - |s[i] - s[j]|)`. If we have enough budget (`rem_k >= cost`), we can form a palindrome of length `2` plus the length of the LPS from the inner substring `s[i+1...j-1]` with the remaining budget `rem_k - cost`. This gives a length of `2 + dp[i+1][j-1][rem_k - cost]`.

The value `dp[i][j][rem_k]` will be the maximum of these options. The final answer is the value for the entire string `s[0...n-1]` with the initial budget `k`, which is `dp[0][n-1][k]`.

```java
class Solution {
    private int cost(char c1, char c2) {
        int diff = Math.abs(c1 - c2);
        return Math.min(diff, 26 - diff);
    }

    public int longestPalindromeSubsequence(String s, int k) {
        int n = s.length();
        int[][][] dp = new int[n][n][k + 1];

        for (int i = n - 1; i >= 0; i--) {
            // Base case: len = 1, s[i...i]
            for (int rem_k = 0; rem_k <= k; rem_k++) {
                dp[i][i][rem_k] = 1;
            }

            for (int j = i + 1; j < n; j++) {
                for (int rem_k = 0; rem_k <= k; rem_k++) {
                    // Option 1 & 2: Skip s[i] or s[j]
                    int result = Math.max(dp[i + 1][j][rem_k], dp[i][j - 1][rem_k]);

                    // Option 3: Match s[i] and s[j]
                    int matchCost = cost(s.charAt(i), s.charAt(j));
                    if (rem_k >= matchCost) {
                        int innerLength = (i + 1 > j - 1) ? 0 : dp[i + 1][j - 1][rem_k - matchCost];
                        result = Math.max(result, 2 + innerLength);
                    }
                    dp[i][j][rem_k] = result;
                }
            }
        }

        return dp[0][n - 1][k];
    }
}
```
### Algorithm
- Define a 3D DP table `dp[n][n][k+1]`, where `dp[i][j][rem_k]` stores the maximum length of a palindromic subsequence for the substring `s[i...j]` using at most `rem_k` operations.
- Initialize the DP table with 0s.
- Iterate through the string `s` with a decreasing outer loop for the start index `i` (from `n-1` to `0`) and an increasing inner loop for the end index `j` (from `i` to `n-1`).
- For each pair `(i, j)`, iterate through all possible remaining costs `rem_k` from `0` to `k`.
- **Base Case**: If `i == j`, the longest palindromic subsequence has length 1. So, `dp[i][i][rem_k] = 1` for all `rem_k`.
- **Recursive Step**: For `i < j`, calculate `dp[i][j][rem_k]` by considering three possibilities:
  1. Skip character `s[i]`: The length would be `dp[i+1][j][rem_k]`.
  2. Skip character `s[j]`: The length would be `dp[i][j-1][rem_k]`.
  3. Match characters `s[i]` and `s[j]`: Calculate the cost `c` to make them identical. If `rem_k >= c`, the length is `2 + dp[i+1][j-1][rem_k - c]`. The inner part `dp[i+1][j-1]` corresponds to an empty substring (length 0) if `j = i+1`.
- `dp[i][j][rem_k]` is the maximum of the outcomes from these choices.
- The final answer is `dp[0][n-1][k]`.

## Space-Optimized 3D Dynamic Programming
The 3D DP approach is correct but uses a large amount of memory. We can optimize the space complexity by observing the dependencies in the DP state transitions. The calculation for `dp[i][...][...]` (row `i`) only depends on values from `dp[i+1][...][...]` (the previous row) and values already computed in the current row `i`. This means we don't need to store the entire 3D table. We only need to keep track of the results for the current row and the previous row, reducing the space complexity significantly.
**Time:** O(n^2 * k). The number of calculations remains the same as the unoptimized approach. · **Space:** O(n * k). We only need two 2D tables of size `n x (k+1)` to store the results for the current and previous rows of the main DP table.
**Pros:** Significantly more memory-efficient than the unoptimized version.; Maintains the same time complexity while being more practical for the given constraints.
**Cons:** The code can be slightly more complex to reason about due to the reduced dimensions and pointer/array swapping.
### Explanation
We can implement the space optimization by maintaining two 2D arrays. Let's call them `dp` and `prev_dp`. `prev_dp` will store the DP values for the row `i+1`, while `dp` will be used to compute the values for the current row `i`.

We iterate `i` from `n-1` down to `0`. In each iteration:
1. `dp` is used to calculate the results for the current row `i`.
2. The values needed from row `i+1` are retrieved from `prev_dp`.
3. After row `i` is fully computed in `dp`, we no longer need the results from `i+1`. So, `dp` becomes the `prev_dp` for the next iteration (`i-1`). This can be done by swapping pointers or copying the array.

This reduces the space from `O(n^2 * k)` to `O(n * k)`, making the solution much more memory-efficient and practical for the given constraints.

```java
class Solution {
    private int cost(char c1, char c2) {
        int diff = Math.abs(c1 - c2);
        return Math.min(diff, 26 - diff);
    }

    public int longestPalindromeSubsequence(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n][k + 1];

        for (int i = n - 1; i >= 0; i--) {
            int[][] current_dp = new int[n][k + 1];
            // Base case: len = 1, s[i...i]
            for (int rem_k = 0; rem_k <= k; rem_k++) {
                current_dp[i][rem_k] = 1;
            }

            for (int j = i + 1; j < n; j++) {
                for (int rem_k = 0; rem_k <= k; rem_k++) {
                    // dp is prev_dp (row i+1), current_dp is for row i
                    // Option 1 & 2: Skip s[i] or s[j]
                    int result = Math.max(dp[j][rem_k], current_dp[j - 1][rem_k]);

                    // Option 3: Match s[i] and s[j]
                    int matchCost = cost(s.charAt(i), s.charAt(j));
                    if (rem_k >= matchCost) {
                        int innerLength = (i + 1 > j - 1) ? 0 : dp[j - 1][rem_k - matchCost];
                        result = Math.max(result, 2 + innerLength);
                    }
                    current_dp[j][rem_k] = result;
                }
            }
            dp = current_dp;
        }

        return dp[n - 1][k];
    }
}
```
### Algorithm
- Instead of a full 3D DP table, use two 2D tables: `dp[n][k+1]` to store results for the current row `i`, and `prev_dp[n][k+1]` to store results for the previous row `i+1`.
- Iterate `i` from `n-1` down to `0`.
- At the beginning of each `i` iteration, `prev_dp` holds the computed values for row `i+1`.
- Compute the values for the current row `i` and store them in `dp`.
- The recurrence relation is modified to use the 2D tables:
  - `dp[i+1][j]` becomes `prev_dp[j]`
  - `dp[i][j-1]` becomes `dp[j-1]`
  - `dp[i+1][j-1]` becomes `prev_dp[j-1]`
- After iterating through `j` for a given `i`, the `dp` table is complete for row `i`. It then becomes the `prev_dp` for the next iteration (`i-1`).
- The final answer is `prev_dp[n-1][k]` after the main loop finishes (as it will hold the results for `i=0`).

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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

```