#419. 最少修改成回文串

最少修改成回文串

题目描述

小明正在整理一串由小写英文字母组成的暗号,但这串暗号还不是回文字符串。

回文字符串是指从左往右读和从右往左读完全相同的字符串。例如,aba、abba 都是回文字符串。

你可以进行若干次修改。每次修改可以选择字符串中的一个位置,将这个位置的字符改成任意一个小写英文字母。

请你计算,至少需要修改多少个字符,才能使整个字符串变成回文字符串。

输入格式

输入一行一个非空字符串 s,仅包含小写英文字母。

输出格式

输出一个整数,表示将 s 变成回文字符串所需的最少修改次数。

样例 #1

abca
1

样例 #2

abcde
2

样例 #3

racecar
0

说明

对于样例 1,可以将 b 改成 c,得到 acca,只需要修改 1 次。

对于样例 2,例如将字符串改成 abcba,需要修改 2 次。

对于样例 3,字符串本身已经是回文字符串,因此不需要修改。

数据范围

  • 1 ≤ |s| ≤ 100000;
  • s 仅包含小写英文字母 a 到 z。

时间限制: 1 秒。空间限制: 256 MiB。