0% completed
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:
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.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible