Problem M
Alchemy
You just finished day one of your alchemy class! For your alchemy homework, you have been given a string of lowercase letters and wish to make it a palindrome. You’re only a beginner at alchemy though, so your powers are limited. In a single operation, you may choose exactly two adjacent letters and change each of them into a different lowercase letter. The resulting characters may be the same as or different from one another, so long as they were both changed by the operation.
Formally, if the string before the operation is $s$ and you chose to change characters $s_ i$ and $s_{i+1}$ to produce string $t$, then $s_ i \neq t_ i$ and $s_{i+1} \neq t_{i+1}$ must be true, but $t_ i = t_{i+1}$ is permitted.
Compute the minimum number of operations needed to make the string a palindrome.
Input
The single line of input contains a string of $n$ $(2 \le n \le 100)$ lowercase letters, the string you are converting into a palindrome.
Output
Output a single integer, which is the minimum number of operations needed to make the string a palindrome.
Sample Input 1 | Sample Output 1 |
---|---|
ioi |
0 |
Sample Input 2 | Sample Output 2 |
---|---|
noi |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
ctsc |
1 |
Sample Input 4 | Sample Output 4 |
---|---|
fool |
2 |
Sample Input 5 | Sample Output 5 |
---|---|
vetted |
2 |