3472. Longest Palindromic Subsequence After at Most K Operations LeetCode Solution

In this guide, you will get 3472. Longest Palindromic Subsequence After at Most K Operations LeetCode Solution with the best time and space complexity. The solution to Longest Palindromic Subsequence After at Most K Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Longest Palindromic Subsequence After at Most K Operations solution in C++
4. Longest Palindromic Subsequence After at Most K Operations solution in Java
5. Longest Palindromic Subsequence After at Most K Operations solution in Python
6. Additional Resources

Problem Statement of Longest Palindromic Subsequence After at Most K Operations

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.

Complexity Analysis

• Time Complexity: O(n^2k)
• Space Complexity: O(n^2k)

3472. Longest Palindromic Subsequence After at Most K Operations LeetCode Solution in C++

class Solution {
 public:
  // Similar to 516. Longest Palindromic Subsequence
  int longestPalindromicSubsequence(string s, int k) {
    const int n = s.length();
    vector<vector<vector<int>>> mem(
        n, vector<vector<int>>(n, vector<int>(k + 1, -1)));
    return lps(s, 0, n - 1, k, mem);
  }

 private:
  // Returns the length of LPS(s[i..j]) with at most `op` operations.
  int lps(const string& s, int i, int j, int op,
          vector<vector<vector<int>>>& mem) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (mem[i][j][op] != -1)
      return mem[i][j][op];
    if (s[i] == s[j])
      return mem[i][j][op] = 2 + lps(s, i + 1, j - 1, op, mem);
    mem[i][j][op] = max(lps(s, i + 1, j, op, mem), lps(s, i, j - 1, op, mem));
    const int cost = getCost(s[i], s[j]);
    if (cost <= op)
      mem[i][j][op] =
          max(mem[i][j][op], 2 + lps(s, i + 1, j - 1, op - cost, mem));
    return mem[i][j][op];
  }

  int getCost(char a, char b) {
    const int dist = abs(a - b);
    return min(dist, 26 - dist);
  }
};
/* code provided by PROGIEZ */

3472. Longest Palindromic Subsequence After at Most K Operations LeetCode Solution in Java

class Solution {
  // Similar to 516. Longest Palindromic Subsequence
  public int longestPalindromicSubsequence(String s, int k) {
    final int n = s.length();
    Integer[][][] mem = new Integer[n][n][k + 1];
    return lps(s, 0, n - 1, k, mem);
  }

  // Returns the length of LPS(s[i..j]) with at most `op` operations.
  private int lps(String s, int i, int j, int op, Integer[][][] mem) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (mem[i][j][op] != null)
      return mem[i][j][op];
    if (s.charAt(i) == s.charAt(j))
      return mem[i][j][op] = 2 + lps(s, i + 1, j - 1, op, mem);
    mem[i][j][op] = Math.max(lps(s, i + 1, j, op, mem), lps(s, i, j - 1, op, mem));
    final int cost = getCost(s.charAt(i), s.charAt(j));
    if (cost <= op)
      mem[i][j][op] = Math.max(mem[i][j][op], 2 + lps(s, i + 1, j - 1, op - cost, mem));
    return mem[i][j][op];
  }

  private int getCost(char a, char b) {
    final int dist = Math.abs(a - b);
    return Math.min(dist, 26 - dist);
  }
}
// code provided by PROGIEZ

3472. Longest Palindromic Subsequence After at Most K Operations LeetCode Solution in Python

class Solution:
  # Similar to 516. Longest Palindromic Subsequence
  def longestPalindromicSubsequence(self, s: str, k: int) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int, op: int) -> int:
      """Returns the length of LPS(s[i..j]) with at most `op` operations."""
      if i > j:
        return 0
      if i == j:
        return 1
      if s[i] == s[j]:
        return 2 + dp(i + 1, j - 1, op)
      res = max(dp(i + 1, j, op), dp(i, j - 1, op))
      cost = self._getCost(s[i], s[j])
      if cost <= op:
        res = max(res, 2 + dp(i + 1, j - 1, op - cost))
      return res

    return dp(0, len(s) - 1, k)

  def _getCost(self, a: str, b: str) -> int:
    dist = abs(ord(a) - ord(b))
    return min(dist, 26 - dist)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.