# Check if a string is K-Palindrome or not

A string is K-Palindrome if it becomes a palindrome on removing at most k characters from it. Write an algorithm to check if a given string is K-Palindrome or not.

For example,

Input: String – ABCDBA, k = 1
Output: K-Palindrome
Explanation: The string becomes a palindrome by removing either C or D from it

Input: ABCDECA, k = 1
Output: Not a K-Palindrome
Explanation: The string needs at-least 2-removals from it to become a palindrome

By carefully analyzing the problem, we can see that it is a variation of classic Edit Distance Problem where we need to convert the given string into its reverse by removing at most K characters from it (i.e. only delete operation is allowed).

Please note that in order to make the original string and its reverse equal, we need to perform at-most N deletions from the original string and N deletions from the reverse string. Therefore, the expression 2*N <= 2*K is satisfied if the string is K-Palindrome.

## C++

Output:

String is K-Palindrome

## Java

Output:

String is K-Palindrome

The worst case time complexity of the above solution is O(2n). The worst case happens when the string contains all different characters.

The problem has an optimal substructure and also exhibits overlapping subproblems. As both properties of dynamic programming are satisfied, we can save subproblem solutions in memory rather than computed again and again. The dynamic programming is illustrated below which runs in O(n2) time -

## C++

Output:

String is K-Palindrome

## Java

Output:

String is K-Palindrome

We can also use solve this problem by finding Longest palindromic subsequence (LPS) of a string. In order to make a string palindrome, the characters which don't contribute to LPS of the string should be removed. Therefore, a string is K-Palindrome if the difference between the length of LPS and the length of the original string is less than equal to K.

For example, LPS of the string `CABCBC` is `CBBC` and on removing A and C from it, the string becomes a palindrome.

## C++

Output:

String is K-Palindrome

## Java

Output:

String is K-Palindrome

The time complexity of above solution is O(n2) and auxiliary space used is O(n2).

(1 votes, average: 5.00 out of 5)