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:

- Find the reverse of the string
- Do an LCS between the string and its reverse string
- 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions