Home » Interview coding problems/challenges

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]=0;
            for i=0 to l
                DP[0][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[0][i] = 0;

    for (int i = 0; i <= n; i++)
        dp[i][0] = 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