2425 - 回文字符串

题目描述

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

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

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

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

输入

第一行为一个整数n3≤n≤5000),表示给定字符串的长度。

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

输出

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

样例

输入

5
ab3bd

输出

2
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题