Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Minimum Deletions in a String to make it a Palindrome

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

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findMinimumDeletions(self, st):
    def is_palindrom(s):
        i = 0
        j = len(s) - 1
        while i <= j:
          if s[i] != s[j]:
            return False
          i += 1
          j -= 1
        return True
    
    def dp(s, memo):
      if s in memo:
        return memo[s]

      if is_palindrom(s):
        return len(s)
      
      max_len = 0
      for i in range(len(s)):
        max_len = max(dp(s[:i] + s[i + 1:], memo), max_len)
      
      memo[s] = max_len

      return max_len
      
    return len(st) - dp(st, {})