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

c++

int dp[202][202][202];
class Solution {
    int helper(string& s, int op, int l, int r) {
        if(l > r) return 0;
        if(dp[op][l][r] != -1) return dp[op][l][r];
        int& res = dp[op][l][r] = max(helper(s,op,l+1,r), helper(s,op,l,r-1));
        int x = abs(s[l] - s[r]), req = min(x, 26 - x);
        if(op >= req) res = max(res, 1 + (l != r) + helper(s,op - req, l + 1, r - 1));
        return res;
    }
public:
    int longestPalindromicSubsequence(string s, int k) {
        memset(dp,-1,sizeof dp);
        return helper(s, k, 0, s.size() - 1);
    }
};