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++

Download   Run Code

Output:

String is K-Palindrome

Java

Download   Run Code

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++

Download   Run Code

Output:

String is K-Palindrome

Java

Download   Run Code

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++

Download   Run Code

Output:

String is K-Palindrome

Java

Download   Run Code

Output:

String is K-Palindrome

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

 
Author: Aditya Goel

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of