Longest Palindromic Subsequence After at Most K Operations

• 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].

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

1class Solution {2    private int cost(char c1, char c2) {3        int diff = Math.abs(c1 - c2);4        return Math.min(diff, 26 - diff);5    }6 7    public int longestPalindromeSubsequence(String s, int k) {8        int n = s.length();9        int[][][] dp = new int[n][n][k + 1];10 11        for (int i = n - 1; i >= 0; i--) {12            // Base case: len = 1, s[i...i]13            for (int rem_k = 0; rem_k <= k; rem_k++) {14                dp[i][i][rem_k] = 1;15            }16 17            for (int j = i + 1; j < n; j++) {18                for (int rem_k = 0; rem_k <= k; rem_k++) {19                    // Option 1 & 2: Skip s[i] or s[j]20                    int result = Math.max(dp[i + 1][j][rem_k], dp[i][j - 1][rem_k]);21 22                    // Option 3: Match s[i] and s[j]23                    int matchCost = cost(s.charAt(i), s.charAt(j));24                    if (rem_k >= matchCost) {25                        int innerLength = (i + 1 > j - 1) ? 0 : dp[i + 1][j - 1][rem_k - matchCost];26                        result = Math.max(result, 2 + innerLength);27                    }28                    dp[i][j][rem_k] = result;29                }30            }31        }32 33        return dp[0][n - 1][k];34    }35}

• 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).

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.

1class Solution {2    private int cost(char c1, char c2) {3        int diff = Math.abs(c1 - c2);4        return Math.min(diff, 26 - diff);5    }6 7    public int longestPalindromeSubsequence(String s, int k) {8        int n = s.length();9        int[][] dp = new int[n][k + 1];10 11        for (int i = n - 1; i >= 0; i--) {12            int[][] current_dp = new int[n][k + 1];13            // Base case: len = 1, s[i...i]14            for (int rem_k = 0; rem_k <= k; rem_k++) {15                current_dp[i][rem_k] = 1;16            }17 18            for (int j = i + 1; j < n; j++) {19                for (int rem_k = 0; rem_k <= k; rem_k++) {20                    // dp is prev_dp (row i+1), current_dp is for row i21                    // Option 1 & 2: Skip s[i] or s[j]22                    int result = Math.max(dp[j][rem_k], current_dp[j - 1][rem_k]);23 24                    // Option 3: Match s[i] and s[j]25                    int matchCost = cost(s.charAt(i), s.charAt(j));26                    if (rem_k >= matchCost) {27                        int innerLength = (i + 1 > j - 1) ? 0 : dp[j - 1][rem_k - matchCost];28                        result = Math.max(result, 2 + innerLength);29                    }30                    current_dp[j][rem_k] = result;31                }32            }33            dp = current_dp;34        }35 36        return dp[n - 1][k];37    }38}