We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Palindromic Subsequence After at Most K Operations

Difficulty: Medium

Problem Description

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'). Return the length of the longest palindromic subsequence of s that can be obtained after performing at most k operations.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • A subsequence is derived by deleting some or none of the characters from a string without changing the order of the remaining characters.
  • Replacements are allowed to change characters to any of their adjacent letters in the alphabet.
  • The problem requires a dynamic programming approach to keep track of possible palindromic subsequences while considering the allowed operations.

Space and Time Complexity

Time Complexity: O(n^2 * k), where n is the length of the string s.
Space Complexity: O(n * k), for storing results in a 2D DP table.

Solution

We can use dynamic programming to solve the problem. We maintain a 2D DP table, where dp[i][j][k] represents the longest palindromic subsequence we can achieve from the substring s[i:j] with at most k operations.

  1. Initialize the DP table. If the characters at the current indices are the same, we can include them in our palindromic subsequence.
  2. If they are different, we consider the possibility of changing one of the characters to match the other, which counts as an operation.
  3. Transition through the DP table by expanding the window of the substring and updating the values based on the characters and the number of remaining operations.

Code Solutions

def longest_palindrome_subseq(s: str, k: int) -> int:
    n = len(s)
    dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        for j in range(k + 1):
            dp[i][i][j] = 1  # A single character is a palindrome
    
    for length in range(2, n + 1):  # length of the substring
        for i in range(n - length + 1):
            j = i + length - 1
            for operations in range(k + 1):
                if s[i] == s[j]:
                    dp[i][j][operations] = dp[i + 1][j - 1][operations] + 2
                else:
                    dp[i][j][operations] = max(dp[i + 1][j][operations], dp[i][j - 1][operations])
                    if operations > 0:
                        dp[i][j][operations] = max(dp[i][j][operations], dp[i + 1][j - 1][operations - 1] + 2)
    
    return max(dp[0][n - 1][j] for j in range(k + 1))
← Back to All Questions