Longest Palindromic Subsequence After at Most K Operations

Problem

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.

Examples

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.

Solution

Method 1 – Top Down Dynamic Programming

Intuition

The goal is to find the longest palindromic subsequence from the given string using at most k operations. Each operation allows changing a character to its next or previous letter in the alphabet (with circular wrapping).

The key insight is to compute the minimum cost to make two characters match using circular distance in the alphabet. For any two characters, we can calculate the cost as the minimum of going forward or backward in the circular alphabet. Then we can decide whether to change a pair of characters (if the cost is affordable) or skip one of them to find better matching opportunities later.

Approach

1. Recursive DP Definition: Define solve(i, j, k) that returns the length of the longest palindromic subsequence from substring s[i...j] with at most k operations available.

2. Base Cases:

   • If i > j: No characters remain, return 0
   • If i == j: Single character is always a palindrome, return 1

3. Recursive Choices:

   • Skip a character: Either skip character at index i or j and recurse

   • Match a pair: Calculate the circular distance cost between s[i] and s[j]:

     cost = min(abs(s[i] - s[j]), 26 - abs(s[i] - s[j]))
     

     If cost ≤ available operations, consider matching them and add 2 to the result

4. Memoization: Use 3D DP array dp[i][j][k] to cache results and avoid redundant calculations

5. Return: The result of solve(0, n-1, k) gives the maximum palindromic subsequence length

Code

C++

class Solution {
private:
    int solve(int i, int j, int k, const string& s, vector<vector<vector<int>>>& dp) {
        if (i > j) return 0;
        if (i == j) return 1;
        
        if (dp[i][j][k] != -1) return dp[i][j][k];
        
        // Skip either left or right character
        int ans = max(solve(i + 1, j, k, s, dp), solve(i, j - 1, k, s, dp));
        
        // Calculate cost to match characters at positions i and j
        int cost = min(abs(s[i] - s[j]), 26 - abs(s[i] - s[j]));
        
        // If we can afford the cost, try matching the pair
        if (k >= cost) {
            ans = max(ans, 2 + solve(i + 1, j - 1, k - cost, s, dp));
        }
        
        return dp[i][j][k] = ans;
    }
    
public:
    int longestPalindromicSubsequence(string s, int k) {
        int n = s.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, -1)));
        return solve(0, n - 1, k, s, dp);
    }
};

Go

func longestPalindromicSubsequence(s string, k int) int {
    n := len(s)
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, k+1)
            for l := range dp[i][j] {
                dp[i][j][l] = -1
            }
        }
    }
    
    var solve func(i, j, k int) int
    solve = func(i, j, k int) int {
        if i > j {
            return 0
        }
        if i == j {
            return 1
        }
        
        if dp[i][j][k] != -1 {
            return dp[i][j][k]
        }
        
        // Skip either left or right character
        ans := max(solve(i+1, j, k), solve(i, j-1, k))
        
        // Calculate cost to match characters at positions i and j
        cost := min(abs(int(s[i])-int(s[j])), 26-abs(int(s[i])-int(s[j])))
        
        // If we can afford the cost, try matching the pair
        if k >= cost {
            ans = max(ans, 2+solve(i+1, j-1, k-cost))
        }
        
        dp[i][j][k] = ans
        return ans
    }
    
    return solve(0, n-1, k)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Java

class Solution {
    private int[][][] dp;
    
    private int solve(int i, int j, int k, String s) {
        if (i > j) return 0;
        if (i == j) return 1;
        
        if (dp[i][j][k] != -1) return dp[i][j][k];
        
        // Skip either left or right character
        int ans = Math.max(solve(i + 1, j, k, s), solve(i, j - 1, k, s));
        
        // Calculate cost to match characters at positions i and j
        int cost = Math.min(Math.abs(s.charAt(i) - s.charAt(j)), 
                           26 - Math.abs(s.charAt(i) - s.charAt(j)));
        
        // If we can afford the cost, try matching the pair
        if (k >= cost) {
            ans = Math.max(ans, 2 + solve(i + 1, j - 1, k - cost, s));
        }
        
        return dp[i][j][k] = ans;
    }
    
    public int longestPalindromicSubsequence(String s, int k) {
        int n = s.length();
        dp = new int[n][n][k + 1];
        
        // Initialize dp array with -1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        
        return solve(0, n - 1, k, s);
    }
}

Kotlin

class Solution {
    private lateinit var dp: Array<Array<Array<Int>>>
    
    private fun solve(i: Int, j: Int, k: Int, s: String): Int {
        if (i > j) return 0
        if (i == j) return 1
        
        if (dp[i][j][k] != -1) return dp[i][j][k]
        
        // Skip either left or right character
        var ans = maxOf(solve(i + 1, j, k, s), solve(i, j - 1, k, s))
        
        // Calculate cost to match characters at positions i and j
        val cost = minOf(kotlin.math.abs(s[i].code - s[j].code), 
                        26 - kotlin.math.abs(s[i].code - s[j].code))
        
        // If we can afford the cost, try matching the pair
        if (k >= cost) {
            ans = maxOf(ans, 2 + solve(i + 1, j - 1, k - cost, s))
        }
        
        dp[i][j][k] = ans
        return ans
    }
    
    fun longestPalindromicSubsequence(s: String, k: Int): Int {
        val n = s.length
        dp = Array(n) { Array(n) { Array(k + 1) { -1 } } }
        return solve(0, n - 1, k, s)
    }
}

Python

class Solution:
    def longestPalindromicSubsequence(self, s: str, k: int) -> int:
        n = len(s)
        dp = {}
        
        def solve(i: int, j: int, k: int) -> int:
            if i > j:
                return 0
            if i == j:
                return 1
            
            if (i, j, k) in dp:
                return dp[(i, j, k)]
            
            # Skip either left or right character
            ans = max(solve(i + 1, j, k), solve(i, j - 1, k))
            
            # Calculate cost to match characters at positions i and j
            cost = min(abs(ord(s[i]) - ord(s[j])), 26 - abs(ord(s[i]) - ord(s[j])))
            
            # If we can afford the cost, try matching the pair
            if k >= cost:
                ans = max(ans, 2 + solve(i + 1, j - 1, k - cost))
            
            dp[(i, j, k)] = ans
            return ans
        
        return solve(0, n - 1, k)

Rust

use std::collections::HashMap;

impl Solution {
    pub fn longest_palindromic_subsequence(s: String, k: i32) -> i32 {
        let chars: Vec<char> = s.chars().collect();
        let n = chars.len();
        let mut dp = HashMap::new();
        
        fn solve(
            i: usize, j: usize, k: i32, chars: &[char],
            dp: &mut HashMap<(usize, usize, i32), i32>
        ) -> i32 {
            if i > j {
                return 0;
            }
            if i == j {
                return 1;
            }
            
            if let Some(&cached) = dp.get(&(i, j, k)) {
                return cached;
            }
            
            // Skip either left or right character
            let mut ans = solve(i + 1, j, k, chars, dp).max(solve(i, j - 1, k, chars, dp));
            
            // Calculate cost to match characters at positions i and j
            let diff = (chars[i] as i32 - chars[j] as i32).abs();
            let cost = diff.min(26 - diff);
            
            // If we can afford the cost, try matching the pair
            if k >= cost {
                ans = ans.max(2 + solve(i + 1, j - 1, k - cost, chars, dp));
            }
            
            dp.insert((i, j, k), ans);
            ans
        }
        
        solve(0, n - 1, k, &chars, &mut dp)
    }
}

TypeScript

function longestPalindromicSubsequence(s: string, k: number): number {
    const n = s.length;
    const dp = new Map<string, number>();
    
    function solve(i: number, j: number, k: number): number {
        if (i > j) return 0;
        if (i === j) return 1;
        
        const key = `${i},${j},${k}`;
        if (dp.has(key)) return dp.get(key)!;
        
        // Skip either left or right character
        let ans = Math.max(solve(i + 1, j, k), solve(i, j - 1, k));
        
        // Calculate cost to match characters at positions i and j
        const diff = Math.abs(s.charCodeAt(i) - s.charCodeAt(j));
        const cost = Math.min(diff, 26 - diff);
        
        // If we can afford the cost, try matching the pair
        if (k >= cost) {
            ans = Math.max(ans, 2 + solve(i + 1, j - 1, k - cost));
        }
        
        dp.set(key, ans);
        return ans;
    }
    
    return solve(0, n - 1, k);
}

Complexity

• ⏰ Time complexity: O(n² * k), where n is the length of s. Each state is computed once due to memoization.
• 🧺 Space complexity: O(n² * k), for the memoization table storing all possible states.

Method 2 – Bottom Up Dynamic Programming

Intuition

Instead of using recursion with memoization, we can build the solution iteratively from smaller subproblems to larger ones. We fill the DP table in a specific order to ensure that when we compute dp[i][j][op], all the required subproblems have already been computed.

Approach

1. DP Definition: dp[i][j][op] represents the length of the longest palindromic subsequence in substring s[i...j] using at most op operations.

2. Initialization:

   • dp[i][i][op] = 1 for all valid i and op (single character is always a palindrome)
   • All other entries start as 0

3. Fill Order: Process by increasing substring length (gap between i and j)

4. Transitions: For each dp[i][j][op]:

   • Skip characters: dp[i][j][op] = max(dp[i+1][j][op], dp[i][j-1][op])
   • Match pair: If cost ≤ op, then dp[i][j][op] = max(dp[i][j][op], 2 + dp[i+1][j-1][op-cost])

5. Result: Maximum value in dp[0][n-1][0...k]

Code

C++

class Solution {
public:
    int longestPalindromicSubsequence(string s, int k) {
        int n = s.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, 0)));
        
        // Base case: single characters
        for (int i = 0; i < n; i++) {
            for (int op = 0; op <= k; op++) {
                dp[i][i][op] = 1;
            }
        }
        
        // Fill DP table for increasing substring lengths
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int op = 0; op <= k; op++) {
                    // Skip characters
                    dp[i][j][op] = max(dp[i + 1][j][op], dp[i][j - 1][op]);
                    
                    // Try to match characters at i and j
                    int cost = min(abs(s[i] - s[j]), 26 - abs(s[i] - s[j]));
                    if (op >= cost) {
                        dp[i][j][op] = max(dp[i][j][op], 2 + dp[i + 1][j - 1][op - cost]);
                    }
                }
            }
        }
        
        // Find maximum result
        int result = 0;
        for (int op = 0; op <= k; op++) {
            result = max(result, dp[0][n - 1][op]);
        }
        return result;
    }
};

Python

class Solution:
    def longestPalindromicSubsequence(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]
        
        # Base case: single characters
        for i in range(n):
            for op in range(k + 1):
                dp[i][i][op] = 1
        
        # Fill DP table for increasing substring lengths
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                for op in range(k + 1):
                    # Skip characters
                    dp[i][j][op] = max(dp[i + 1][j][op], dp[i][j - 1][op])
                    
                    # Try to match characters at i and j
                    cost = min(abs(ord(s[i]) - ord(s[j])), 26 - abs(ord(s[i]) - ord(s[j])))
                    if op >= cost:
                        dp[i][j][op] = max(dp[i][j][op], 2 + dp[i + 1][j - 1][op - cost])
        
        # Find maximum result
        return max(dp[0][n - 1][op] for op in range(k + 1))

Complexity

• ⏰ Time complexity: O(n² * k), same as top-down approach but with better constant factors.
• 🧺 Space complexity: O(n² * k), for the 3D DP table.

Comparison: Top-Down vs Bottom-Up

Aspect	Top-Down (Memoization)	Bottom-Up (Tabulation)
Implementation	More intuitive, follows problem structure	Requires careful ordering of subproblems
Space Usage	May use less space (only needed states)	Always uses full O(n²k) space
Performance	Recursion overhead	Better constant factors, no function calls
Stack Usage	O(n) recursion stack	O(1) additional stack space
Debugging	Easier to trace problem flow	More complex to debug state transitions