# Minimum number of deletions to make a string palindrome

In this article, we are going to see how to find the minimum number of deletions to make a string palindrome? This is a standard interview problem already featured in many company coding rounds.
Submitted by Radib Kar, on April 22, 2020

Problem statement:

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

Solution Approach:

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

```    LPS(s) = LCS(s,reverse(s))

Where,
LPS(s) = longest palindromic subsequence for string s
LCS(s,reverse(s)) = Longest Common subsequence for
string s and reverse of string s
```

So, to find the longest palindromic subsequence:

1. Find the reverse of the string
2. Do an LCS between the string and its reverse string
3. Result=string length-longest palindromic subsequence length

1) To find the reverse of the string

```    string reverse(string s,int n){
string p="";
for(int i=n-1;i>=0;i--)
p+=string(1,s[i]); //append characters from last
return p;
}
```

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

```    L = length of the string,reverse of the string
Str1 = string itself
Str2 = Reverse of the string

1.  Initialize DP[l+1][l+1]  to 0
2.  Convert the base case of recursion:
for i=0 to l
DP[i]=0;
for i=0 to l
DP[i]=0;

Fill the DP table
for i=1 to l    //i be the subproblem length for the string
for j=1 to l //j be the subproblem length for reverse of the string
if(str1[i-1]==str2[j-1])
DP[i][j]=DP[i-1][j-1]+1;
else
DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
end for
end for

4.  The final output will be DP[l][l]

Final step is to return minimum number of deletion which l-DP[l][l]

This will lead to the final result.
```

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,

```    LPS(I,j) = LPS(i+1,j-1)+2
if
str1[i] == str[j]
Else
LPS(I,j) = max(LPS(i+1,j), LPS(i,j-1))
```

Convert the above recursion into DP while taking care of base cases.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

string reverse(string s, int n)
{
string p = "";

for (int i = n - 1; i >= 0; i--)
p += string(1, s[i]);

return p;
}

//LCS of the strings
int LCS(string s1, string s2, int n)
{

int dp[n + 1][n + 1];

for (int i = 0; i <= n; i++)
dp[i] = 0;

for (int i = 0; i <= n; i++)
dp[i] = 0;

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = std::max(dp[i][j - 1], dp[i - 1][j]);
}
}

return dp[n][n];
}

int main()
{

string s1;

cout << "Enter string:\n";
cin >> s1;

int n = s1.length();

//reverse of string
string s2 = reverse(s1, n);

//find LCS of the strings, result=n-LCS(s1,s2)
cout << "minimum characters to remove " << n - LCS(s1, s2, n) << endl;

return 0;
}
```

Output

```Enter string:
includecpni
minimum characters to remove 4
```