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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Palindromic Subsequence After at Most K Operations

Number: 3786

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a string s and an integer k, you are allowed to perform at most k operations on s. In one operation, you can replace any character with its next or previous letter in the alphabet (using wrap‐around, so that after z comes a and before a comes z). Your goal is to maximize the length of a palindromic subsequence that can be obtained from s after using at most k operations.

For example, if s = "abced" and k = 2, one way to achieve a palindrome of length 3 is by performing operations to eventually have "accec", from which the subsequence "ccc" forms a palindrome. In another example, s = "aaazzz" with k = 4 can be transformed into "zaaaaz" where the whole string is a palindrome of length 6.

Key Insights

  • The operations allow you to adjust individual characters at a cost equal to the minimum number of moves (taking wrap-around into account) needed to match two characters.
  • The problem is a variation of the classic longest palindromic subsequence (LPS) but with an added twist: each pair or single character may need some operations to become palindromic.
  • A key observation is that for any pair of characters, the minimum number of operations needed to make them identical is: min(|s[i] – s[j]|, 26 – |s[i] – s[j]|).
  • A dynamic programming (DP) approach that considers intervals along with the cost incurred is natural. The state can track the current interval (i, j) and the remaining (or used) operations.
  • Instead of computing the subsequence directly, one can design a DP that returns, for each substring, the maximum palindromic subsequence length that can be obtained using at most a given number of operations.
  • The solution involves “merging” results from two ends of the string and deciding whether to use a pair (if the cost to match is affordable) or to skip one of the characters.

Space and Time Complexity

Time Complexity: O(n² * k), where n is the length of the string and k is the maximum number of operations. Space Complexity: O(n² * k), due to the DP table dimensions storing solutions for each interval and each possible cost up to k.

Solution

We use a three-dimensional DP approach where dp[i][j][r] represents the maximum length of a palindromic subsequence that can be obtained from the substring s[i...j] when we are allowed to use at most r operations.

  1. Base cases:

    • If i > j, the subsequence is empty (length 0).
    • If i == j, a single character forms a palindrome of length 1 (and it doesn’t require any operation).

  2. For each DP state corresponding to indices (i, j) with available operations r, we have two main choices:

    • Skip s[i] or skip s[j] to potentially find a longer palindrome in a smaller interval.
    • If we take both characters, calculate the cost to convert s[i] and s[j] into the same letter. The cost is: cost = min( abs(s[i] - s[j]), 26 - abs(s[i] - s[j]) ). If r >= cost, then we consider dp[i+1][j-1][r-cost] and add 2 (for the pair) to form a candidate solution.

  3. The answer is dp[0][n-1][k], where n is the length of the string.

A common trick is to iterate intervals in increasing length (from small substrings up to the entire string) to ensure all necessary subproblems are already computed.

Below are code solutions in four languages with detailed comments.

Code Solutions

# Python solution for "Longest Palindromic Subsequence After at Most K Operations"
def longest_palindrome_subseq(s: str, k: int) -> int:
    n = len(s)
    # dp[i][j][r] represents the maximum length using substring s[i...j] with at most r operations.
    dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]
    
    # Base case: single character is a palindrome of length 1 (no cost needed)
    for i in range(n):
        for r in range(k + 1):
            dp[i][i][r] = 1
    
    # Function to compute cost to match two letters (with wrap-around)
    def cost_to_match(a, b):
        diff = abs(ord(a) - ord(b))
        return min(diff, 26 - diff)
    
    # Process all substring lengths starting from length 2
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # For each available operations r from 0 to k
            for r in range(k + 1):
                # Option 1: skip s[i]
                option1 = dp[i + 1][j][r] if i + 1 <= j else 0
                # Option 2: skip s[j]
                option2 = dp[i][j - 1][r] if i <= j - 1 else 0
                best = max(option1, option2)
                # Option 3: use s[i] and s[j] by converting them to the same character
                c = cost_to_match(s[i], s[j])
                if r >= c:
                    inner = dp[i + 1][j - 1][r - c] if i + 1 <= j - 1 else 0
                    best = max(best, inner + 2)
                dp[i][j][r] = best
                
    return dp[0][n - 1][k]

# Example usage:
print(longest_palindrome_subseq("abced", 2))  # Expected output: 3
print(longest_palindrome_subseq("aaazzz", 4))  # Expected output: 6
← Back to All Questions