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.
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".
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.
Print YES if the given string is K-palindrome else print NO. Print the answer for each test case in a new line.
1<= T <=100 1<= N, K <=1000
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 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.
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):
C++ Implementation (Dynamic Programming Approach):
(a) Top Down Approach:
(b) Bottom Up Approach
Output:need an explanation for this answer? contact us directly to get an explanation for this answer