Minimum Deletions to Make Palindrome

Problem

Return the minimum number of characters to delete from s so that the remaining string is a palindrome.

The answer is len(s) minus the longest palindromic subsequence, computed with interval DP. An empty string needs zero deletions.

Hint

Deleting all characters except a longest palindromic subsequence is optimal.

case 1

in: ["aab"]

expected: 1

case 2

in: ["abca"]

expected: 1

case 3

in: ["abcde"]

expected: 4

case 4

in: [""]

expected: 0

case 5

in: ["aba"]

expected: 0

Starter codePython

def min_deletions_palindrome(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor