Minimum Insertions to Palindrome

Given a string ( s ), your task is to determine the minimum number of insertions required to transform ( s ) into a palindrome. A palindrome is a string that reads the same backward as forward. You can insert characters at any position in the string. For instance, if ( s = \texttt{race} ), the minimum number of insertions is 3, as one possible solution is to insert characters to form ( \texttt{ecarace} ). This problem requires a dynamic programming approach to efficiently compute the answer for input strings of moderate length.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing the non-empty string ( s ). The string can contain any visible characters without spaces.

outputFormat

Output the minimum number of insertions required to convert the given string into a palindrome. The output should be printed to standard output (stdout) as an integer.## sample

race

3