Minimum Insertions to Form a Palindrome

You are given a string S. Your task is to determine the minimum number of characters that need to be inserted to transform S into a palindrome. A palindrome is a string that reads the same backwards and forwards, i.e., \(S = S^R\), where \(S^R\) denotes the reverse of \(S\).

The problem can be solved efficiently using dynamic programming. Let \(dp[i][j]\) represent the minimum number of insertions required to convert the substring \(S[i \ldots j]\) into a palindrome. The final answer will be \(dp[0][n-1]\) for a string of length \(n\). Both time and space complexities are \(O(n^2)\).

Be sure to read input from standard input (stdin) and write your answer to standard output (stdout).

inputFormat

The input consists of a single line containing the string S (\(1 \leq |S| \leq 10^3\)), which is composed of lowercase English letters.

outputFormat

Output a single integer that represents the minimum number of character insertions needed to convert the string S into a palindrome.

abca

1