Q:

Given a string, find out if the string is K-palindrome or not. A k-palindrome string transforms into a palindrome on removing at most k characters from it

mahmoud2506
Save to bookmark
|
2022-05-01
|
  276 
0

K-Palindromic String

Given a string, find out if the string is K-palindrome or not. A k-palindrome string transforms into a palindrome on removing at most k characters from it.

Problem description:

The given problem needs knowledge of palindrome, which is a string whose structure from first to the last traversal is the same as traversal from last to the first position.

You have to check if the given string is K-palindrome it means after removing at maximum k number of characters from the string is converted into some kind of palindrome. If possible then print "YES" otherwise print "NO".

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the integers N and K where N denotes the length of the string.

The second line of each test case contains the string.

Output:

Print YES if the given string is K-palindrome else print NO. Print the answer for each test case in a new line.

Constraints:

1<= T <=100
1<= N, K <=1000

Examples:

Input:
T=1
abcdedecbaef
k=3

Output:
YES

Input:
T=1
abcde
k=3

Output:
NO
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
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

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
You are given a staircase, you need to find the to... >>
<< You are given a list of jobs where each job has a ...