Scale Engineer

Longest Palindromic Subsequence After at Most K Operations

Med
#3087Time: 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)`.
Patterns
Dynamic Programming
Data structures
String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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

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

Complexity

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

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem