Minimum Changes to Make a Palindrome

Given a string s, determine the minimum number of changes required to convert it into a palindrome. You are allowed to perform the following operations on the string:

• Insertion of a character
• Deletion of a character
• Replacement of a character

The goal is to find the minimum number of operations needed. The problem can be formulated using dynamic programming. In particular, one can define a DP table, where the entry $\text{dp}[i][j]$ denotes the minimum changes required to make the substring from index $i$ to index $j$ a palindrome.

For example, for the input string race, the answer is 2 because with 2 changes (e.g., performing a replacement on the first and last characters or a combination of insertions/deletions), the string can be converted into a palindrome.

inputFormat

The input consists of a single line containing the string s. The string will have a length between 1 and 1000 characters.

outputFormat

Output a single integer on a new line, representing the minimum number of changes required to make the given string a palindrome.

race

2