Grokking Dynamic Programming Patterns for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Minimum Deletions in a String to make it a Palindrome
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a string, find the minimum number of characters that we can remove to make it a palindrome.

Example 1:

Input: "abdbca"
Output: 1
Explanation: By removing "c", we get a palindrome "abdba".

Example 2:

Input: = "cddpd"
Output: 2
Explanation: Deleting "cp", we get a palindrome "ddd".

Example 3:

Input: = "pqr"
Output: 2
Explanation: We have to remove any two characters to get a palindrome, e.g. if we 
remove "pq", we get palindrome "r".

Constraints:

  • 1 <= st.length <= 1000
  • st consists only of lowercase English letters.

Solution

This problem can be easily converted to the "Longest Palindromic Subsequence" (LPS) problem. We can use the fact that LPS is the best subsequence we can have, so any character that is not part of LPS must be removed. Please note that it is 'Longest Palindromic SubSequence' and not 'Longest Palindrome Substring'.

So, our solution for a given string 'st' will be:

    Minimum_deletions_to_make_palindrome = Length(st) - LPS(st)

Code

Let's jump directly to bottom-up dynamic programming:

Python3
Python3
. . . .

The time and space complexity of the above algorithm is O(n^2), where 'n' is the length of the input string.

Similar problems

Here are a couple of similar problems:

1. Minimum insertions in a string to make it a palindrome

Will the above approach work if we make insertions instead of deletions?

Yes, the length of the Longest Palindromic Subsequence is the best palindromic subsequence we can have. Let's take a few examples:

Example 1:

Input: "abdbca"   
Output: 1

Explanation: By inserting "c", we get a palindrome "a<span style="color:red;font-weight:bold">c</span>bdbca".

Example 2:

Input: = "cddpd"  
Output: 2

Explanation: Inserting "cp", we get a palindrome "cd<span style="color:red;font-weight:bold">p</span>dpd<span style="color:red;font-weight:bold">c</span>". We can also get a palindrome by inserting "dc": "cddpd<span style="color:red;font-weight:bold">dc</span>"

Example 3:

Input: = "pqr"  
Output: 2

Explanation: We have to insert any two characters to get a palindrome (e.g. if we insert "pq", we get a palindrome "pqr<span style="color:red;font-weight:bold">qp</span>").

2. Find if a string is K-Palindromic

Any string will be called K-palindromic if it can be transformed into a palindrome by removing at most 'K' characters from it.

This problem can easily be converted to our base problem of finding the minimum deletions in a string to make it a palindrome. If the "minimum deletion count" is not more than 'K', the string will be K-Palindromic.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible