Minimum Deletions to Make a Palindrome

Given a string (s), your task is to determine the minimum number of characters that need to be deleted so that the remaining string becomes a palindrome. A palindrome is a string that reads the same both forwards and backwards.

The key idea is to compute the length of the (\text{Longest Palindromic Subsequence (LPS)}) using dynamic programming and then subtract its length from (n) (the length of (s)). The answer is given by (n - \text{LPS}).

inputFormat

A single line containing the string (s).

outputFormat

Output a single integer, representing the minimum number of deletions required to convert (s) into a palindrome.## sample

abcba

0