Change string A to B such that it has maximum LCS with K operation

help
, , ,
1

We are given two strings A and B. We are only allowed to change A by increasing the char[i] to the next alphabet in the alphabet series a->b, b->c, z-> a. Or changing to the previous char b->a, a->z.
0 < A.len ,B.len < 100
a <= A[i], B[i] <= z
0 <= k <= 200.
we can use almost k such operations, and find the max lcs we can achieve.

2

The idea is to use Dynamic Programming. Lets define a 3D matrix dp, where dp[i][j][k] defines the Longest Common Subsequence for the first i numbers of the first string, the first j number of the second string when we are allowed to change at max k changes in the first string.
Very similar to this problem: K-ordered-lcs(dynamic programming) - 💡-k-ordered-lcs - Coding Blocks Discussion Forum

#include <iostream>
using namespace std;
#include <bits/stdc++.h>

int helper(int i, int j, string a, string b, int k, vector<vector<vector<int>>> &dp) {
    if(i == a.size() || j == b.size()) {
        return 0;
    }
    if(dp[i][j][k] != -1) {
        return dp[i][j][k];
    }
    int same = 0, change = 0, move_i = 0, move_j = 0;
    
    if(a[i] == b[j]) {
        same = 1 + helper(i+1, j+1, a, b, k, dp);
    }
    else {
        move_i = helper(i+1, j, a, b, k, dp);
        move_j = helper(i, j+1, a, b, k, dp);
        int diff = abs(a[i]-b[j]);
        if(k >= diff) {
            change = 1 + helper(i+1, j+1, a, b, k-diff, dp);
        }
    }
    
    return dp[i][j][k] = max(same, max(change, max(move_i, move_j)));
}

int getMaximumLength(string a, string b, int k) {
    vector<vector<vector<int>>> dp(a.size(), vector<vector<int>>(b.size(), vector<int>(k+1, -1)));
    return helper(0, 0, a, b, k, dp);
}

int main() {
    // Write C++ code here
    //std::cout << "Try programiz.pro";
    string a = "hacker";
    string b = "hacker";
    int k = 10;
    cout<<getMaximumLength(a, b, k)<<endl;
    
    a = "aamge";
    b = "basic";
    k = 8;
    cout<<getMaximumLength(a, b, k)<<endl;
    return 0;
}