Minimum Insertions to Form a Palindrome

Given a string ( s ), determine the minimum number of insertions required to transform ( s ) into a palindrome. A palindrome is a string that reads the same forwards and backwards. You can insert characters at any position in the string to achieve this. The problem can be solved efficiently using dynamic programming with the following recurrence:

[ dp[i][j] = \begin{cases} 0, & \text{if } i \geq j,\ dp[i+1][j-1], & \text{if } s[i]=s[j],\ 1 + \min(dp[i+1][j], dp[i][j-1]), & \text{otherwise.} \end{cases} ]

Your task is to implement this algorithm such that it reads the input from standard input and prints the result to standard output.

inputFormat

The input consists of a single line containing the string ( s ). ( s ) contains only lowercase English letters and its length does not exceed ( 10^3 ).

outputFormat

Output a single integer representing the minimum number of insertions required to convert the given string into a palindrome.## sample

a

0