Minimum Deletions to Form a Palindrome

You are given a string s. Your task is to determine the minimum number of deletions required to transform s into a palindrome.

A palindrome is a string that reads the same backward as forward. For example, the string "racecar" is already a palindrome, whereas the string "abca" can be transformed into a palindrome by deleting one character (for example, removing the character 'b' to form "aca").

Use a dynamic programming approach to solve this challenge efficiently.

inputFormat

The input consists of a single line containing the string s. The string will consist of lowercase English letters only.

outputFormat

Output a single integer representing the minimum number of deletions required to convert s into a palindrome.

abca

1