Minimum Deletions to Palindrome

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

A palindrome is a string that reads the same forwards and backwards. One effective way to solve this problem is to first compute the length of the longest palindromic subsequence (LPS) of s. Then, the minimum number of deletions required is given by:

\(\text{minDeletions} = n - LPS\)

where \(n\) is the length of the string s. Use dynamic programming to compute the LPS efficiently.

inputFormat

The input consists of a single line containing the string s.

Constraints: \(1 \leq |s| \leq 1000\).

outputFormat

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

ababc

2