Minimum Insertions to Form a Palindrome

Given a string consisting of lowercase alphabets, your task is to determine the minimum number of insertions required to convert the string into a palindrome. A palindrome is a sequence that reads the same backward as forward. Insertions can be performed at any position within the string.

We can solve this problem using dynamic programming. Let ( dp[i][j] ) represent the minimum number of insertions needed to make the substring ( s[i\ldots j] ) a palindrome. Then, if ( s[i] = s[j] ), we have ( dp[i][j] = dp[i+1][j-1] ); otherwise, ( dp[i][j] = \min(dp[i+1][j], dp[i][j-1]) + 1 ).

inputFormat

Input is provided via standard input (stdin). It contains a single line with a string of lowercase alphabets.

outputFormat

Output the minimum number of insertions required to transform the given string into a palindrome via standard output (stdout).## sample

ab

1