Grokking Dynamic Programming Interview/

...

/

Minimum Deletions in a String to make it a Palindrome

Minimum Deletions in a String to make it a Palindrome

Let's solve the Minimum Deletions in a String to make it a Palindrome problem using Dynamic Programming.

We'll cover the following...

Statement

You are given a string s. The task is to count the minimum deletions from s such that the resultant string is a palindrome.

Let’s take an example string, “radear”. We can remove the character “e” from this string and we will be left with “radar”, which is a valid palindrome. So, we need minimum of one deletion to make this string a valid palindrome.

Constraints:

  • s contains all lowercase characters.
  • 1≤1 \leq s.length ≤5900\leq 5900

Examples

No.

s

Minimum Deletions

1

aebcbda

2

2

radear

1

3

asseqruqssa

2

4

level

0

Try it yourself

Implement your solution in the following playground.

Press + to interact
Java
usercode > Main.java
import java.util.*;



public class Main{

    public static int minimumDeletions(String s) {



        // Write your code here

    

        return 0;

    }

}
Minimum Deletions in a String to make it a Palindrome

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Palindromic Subsequence dynamic programming pattern.

Naive approach

A naive approach is to generate all the subsequences of the given sequence and find the length of the longest palindromic sequence. Then subtract it from the length of the original sequence to find the minimum deletions. Let’s denote the length of the longest palindromic sequence as LPS.

We can express the number of minimum deletions as:

Length(s)−LPS(s)Length(s) - LPS(s)

The LPS can be solved using recursion. So, to find the LPS of s, we start from the first and the end index of s, and at each recursive step, we follow the following steps:

  • If the start and end indexes are the same, we are at a single character, a palindrome with length 11. So, we return 1.

  • If the elements at the start and end index are the same, we increase the count by 2 and make a recursive call to the rest of the string.

  • If the elements are ...

Access this course and 1400+ top-rated courses and projects.