need an explanation for this answer? contact us directly to get an explanation for this answer

1) Recursive Approach:

This problem is an application of EDIT DISTANCE of dynamic problem, but the main logic here is that we will use one string as the given string and the other string as the reverse of the given string and the only operation that we can perform is delete and no other option of Edit distance logic.

To make the two string equal we need to almost N deletions from each string that is 2*N deletion overall, therefore if 2*N<=2*k then only the string is K-palindrome.

We will follow this algorithm:

if any of the string is empty 
then return total length of
other string.
			
if last character of both string are 
same then recur for remaining character.

if last character are not same then 
first case: remove last character from first
string and recur.
second case: remove last character from 
second string and recur.
return 1+min(first case, second case)

Time Complexity for the above approach in the worst case is exponential.

Space Complexity for the above approach in the worst case is linear.

2) Dynamic Programming Approach:

(a): Top Down Approach:

In this approach we will use memorization method, we will create 2-D dp[n][m] state where initially all the states are filled with -1, then each time we call recurrence function we update the dp[n][m] state, where n is the index for first string and m is the index for the second string.

(b) Bottom Up Approach:

In this approach we will fill the table in bottom up manner, each dp[n][m] state will be filled in bottom up manner as initially for state of length (i==0 or j==0) we will give them the value of other string length(i+j),i.t dp[i][j]=(i+j) if i==0||j==0.

dp[i][j]=(i+j),i==0 or j==0.
if(s1[i-1]==s2[j-1])
    dp[i][j]=dp[i-1][j-1],i>=1 and j>=1
else
    dp[i][j]=1+min(dp[i-1][j],dp[i][j-1])

Here, s1 is given string, s2 is the reversed form of s1, i and j are the length of s1 and s2 at dp[][] state i and j respectively.

Time complexity for the above approach in the worst case is : O(n*n)

Space complexity for the above approach in the worst case is : O(n*n)

C++ Implementation (Recursive Approach):

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

typedef long long ll;

//solve function which will
//return minimum delete operation
//to make two string equal.
ll solve(string s1, string s2, ll n, ll m)
{
    //if either string is of 0 length
    //remove all characters from the
    //other string.
    if (n == 0 || m == 0)
        return (n + m);

    //if last character are same
    //then recur for remaining characters.
    if (s1[n - 1] == s2[m - 1])
        return solve(s1, s2, n - 1, m - 1);
    else //find minimum from two possible case
        //at one if last character of first string is
        //excluded and in other case if last character of
        //second string is excluded.
        return 1 + min(solve(s1, s2, n - 1, m), solve(s1, s2, n, m - 1));
}

int main()
{
    ll t;
    
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        cout << "Enter string: ";
        string s1;
        cin >> s1;
    
        cout << "Enter K: ";
        ll k;
        cin >> k;
    
        //for reversed string.
        string s2 = s1;
        ll n = s1.length();
    
        //reverse.
        reverse(s2.begin(), s2.end());
        if (solve(s1, s2, n, n) <= 2 * k)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }
    
    return 0;
}

Output:

Enter number of test cases: 3
Enter string: abcccdcccab
Enter K: 1
NO
Enter string: abcdba
Enter K: 1
YES
Enter string: include
Enter K: 2
NO

C++ Implementation (Dynamic Programming Approach):

(a) Top Down Approach:

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

typedef long long ll;

//initialize dp state.
ll dp[1003][1003];

//solve function which will
//return minimum delete operation
//to make two string equal.
ll solve(string s1, string s2, ll n, ll m)
{
    //if either string is of 0 length
    //remove all characters from the
    //other string.
    if (n == 0 || m == 0)
        return (n + m);

    //if already calculated then
    //simply return.
    if (dp[n][m] != -1)
        return dp[n][m];

    //if last character are same
    //then recur for remaining characters.
    if (s1[n - 1] == s2[m - 1])
        return dp[n][m] = solve(s1, s2, n - 1, m - 1);
    else //find minimum from two possible case
        //at one if last character of first string is
        //excluded and in other case if last character of
        //second string is excluded.
        return dp[n][m] = 1 + min(solve(s1, s2, n - 1, m), solve(s1, s2, n, m - 1));
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter string: ";
        string s1;
        cin >> s1;

        cout << "Enter K: ";
        ll k;
        cin >> k;

        //for reversed string.
        string s2 = s1;
        ll n = s1.length();

        //initially fill all dp state
        //with -1.
        memset(dp, -1, sizeof(dp));

        //reverse.
        reverse(s2.begin(), s2.end());
        if (solve(s1, s2, n, n) <= 2 * k)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 2
Enter string: abbbaaabbbaaadce
Enter K: 3
NO
Enter string: abcdefghfedcba
Enter K: 3
YES

(b) Bottom Up Approach

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test case: ";
    cin >> t;

    while (t--) {
        cout << "Enter string: ";
        string s1;
        cin >> s1;

        string s2;
        s2 = s1;
        ll k;

        cout << "Enter K: ";
        cin >> k;

        reverse(s2.begin(), s2.end());

        ll n = s1.length();

        //initialise dp state.
        ll dp[n + 1][n + 1];
        for (ll i = 0; i <= n; i++)
            for (ll j = 0; j <= n; j++) {
                //if either of them is 0.
                if (i == 0 || j == 0) {
                    dp[i][j] = (i + j);
                    continue;
                }
                else {
                    //if character matches
                    if (s1[i - 1] == s2[j - 1])
                        dp[i][j] = dp[i - 1][j - 1];
                    else //if there last character does not matches.
                        dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        ll z = dp[n][n];

        //if deletions count is less
        //than 2*k then it is possible to
        //make two string identical.
        if (z <= 2 * k)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }
    
    return 0;
}

Output:

Enter number of test case: 3
Enter string: abcdef
Enter K: 3
NO
Enter string: abcde
Enter K: 3
NO
Enter string: abcdedecbaef
Enter K: 3
YES

need an explanation for this answer? contact us directly to get an explanation for this answer