#T841. 回文修补
回文修补
小艾有一个长度为 的字符串 。如果一个字符串正着读和倒着读完全相同,就称它为回文串,例如 abba 和 abcba 都是回文串,而 abca 不是。
每次操作,小艾可以选中 中恰好一个位置,把这个位置上的字符替换成任意一个小写英文字母。操作不会改变字符串的长度,也不会改变其他位置上的字符。
请你计算:把 变成回文串,至少需要多少次操作?
输入格式
第一行输入一个整数 (),表示字符串的长度。
第二行输入一个字符串 ,长度为 ,仅由小写英文字母 a 到 z 组成,不含空格等空白字符。
输出格式
输出一个整数,表示把 变成回文串所需的最少操作次数,行末换行。
最少操作次数由 唯一确定,因此本题只有一个正确答案,不要输出任何其他内容。
数据范围
- ():字符串长度;
- 的长度恰好为 ;
- 中每个字符都是小写英文字母
a到z。
样例 1
8
abccdzaa
3
按从 开始编号,第 个字符与第 个字符都是 a,这一对已经相同,不需要操作。其余三对对称位置 、、 上的字符分别是 、、,都不相同,所以每一对至少要修改其中一个位置,至少需要 次操作。
另一方面,把第 个字符改成 b、第 个字符改成 c、第 个字符改成 c,得到 abccccba,恰好用了 次操作。因此答案是 。
样例 2
7
abxdcba
1
三对对称位置中,只有第 个字符 x 与倒数第 个字符 c 不同。把 x 改成 c,得到回文串 abcdcba,用了 次操作。正中间的第 个字符 d 与它自身对称,不需要修改。原串不是回文串, 次操作不够,因此答案是 。
相关
在下列比赛中: