# 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

**Example:**

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, basically

So, to find the longest palindromic subsequence:

1) To find the reverse of the string2) LCS between the string and its reverse stringTo 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.

C++ Implementation:

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