Minimum number of deletions to make a string palindrome
Given string str find the minimum number of deletions such that the resultant string is a palindrome.
Input: Each input consists of the string str Output: Print the minimum number of characters to be deleted to make the string a palindrome Constraints: String length will be under 1000
Input: String str: "includecpni" Output: 4
Explanation of Example:
So, we need to find the longest palindromic subsequence and delete the rest of the characters. Here, The longest palindromic sub-sequences are: Inclcni Incucni Incdcni Incecni Incpcni All these are of same length and are palindromes So, minimum characters to delete are 4
We know what's a palindrome is? A palindrome is a string that is the same as its reverse order.
That means to find the longest palindromic subsequence, we need to check the longest common subsequence between the string itself and its reverse string.
So, to find the longest palindromic subsequence:
1) To find the reverse of the string
2) LCS between the string and its reverse string
To detail how to find Longest Common subsequence b/w any two strings, go through this article, Longest Common subsequence
There is another way to find the longest palindromic subsequence, without using LCS. I wouldn't explain the detailed solution, rather try to think and implement your own.
The recursion is,
Convert the above recursion into DP while taking care of base cases.
Outputneed an explanation for this answer? contact us directly to get an explanation for this answer