← 返回题目
题库练习 回文字符串（palindrome）
← 上一题 下一题 →

A71365 | 回文字符串（palindrome）

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

回文字符串指的是对称字符串，也就是该字符串从左到右读和从右到左读得到的结果是一样的。

给定任意的一个字符串，如果该字符串不是回文字符串，通过插入若干字符，可以将该字符串改造为回文字符串。

给定一个字符串，请问该字符串最少插入多少个字符，可以使得该字符串成为回文字符串？

比如：字符串"ab3bd"，在插入2个字符后可以变成一个回文词："dab3bad"或"adb3bda"。然而插入2个以下的字符，无法使其变成一个回文字符串。

输入格式

第一行为一个整数n（3≤n≤5000），表示给定字符串的长度。

第二行为长度为n的不含空格的字符串。

输出格式

一个数，要插入的最少字符数。

输入输出样例

输入 #1
5
ab3bd
输出 #1
2
输入 #2
8
a2bZcba3
输出 #2
3
输入 #3
20
asbdczdgehfxgedc2bas
输出 #3
9
C++ 编辑器
输入
输出