Minimum Insertions to Form a Palindrome

Given a string \( s \), determine the minimum number of insertions required to transform it into a palindrome. A palindrome is a string that reads the same forward and backward. To solve this problem, you can use a dynamic programming approach which considers the following recurrence:

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

For example, for \( s = \texttt{race} \), the answer is 3 because inserting 3 characters can make it a palindrome (for instance, "ecarace").

inputFormat

The input consists of a single line containing the string \( s \). The string contains only lowercase English letters.

outputFormat

Output a single integer: the minimum number of insertions required to transform \( s \) into a palindrome.

race

3