# 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

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:

Time Complexityfor the above approach in the worst case isexponential.Space Complexityfor the above approach in the worst case islinear.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 thedp[n][m]state, wherenis the index for first string andmis 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 stringlength(i+j),i.t dp[i][j]=(i+j) if i==0||j==0.Here,

s1is given string,s2is the reversed form ofs1,iandjare the length ofs1ands2atdp[][]stateiandjrespectively.Time complexityfor the above approach in the worst case is :O(n*n)Space complexityfor the above approach in the worst case is :O(n*n)C++ Implementation (Recursive Approach):Output:C++ Implementation (Dynamic Programming Approach):(a) Top Down Approach:

Output:(b) Bottom Up Approach

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