分数: 500 点
问题陈述
为了表达谢意,高桥决定给Snuke一个等级——K 回文。 A级——L 回文,其中 L 是一个非负整数,定义如下:
- 让 \mathrm{rev}(s) 表示字符串的反转 当 s.
- 一个字符串 s 被认为是回文时 s = \mathrm{rev}(s).
- 空字符串和非回文字符串是 level-0 回文。
- 对于任何 非空 级别-(L-1) 回文 t,串联 t, \mathrm{rev}(t) 按此顺序是一个级别-L 回文。
- 对于任何级别-(L-1) 回文 t 和任何字符 c,串联 t, c, \mathrm{rev}(t) 按此顺序是一个级别-L 回文。
现在,高桥有一根绳子 S。 判断是否可以制作 S 完全水平-K 回文通过执行以下操作零次或多次:选择一个字符 S 并更改为另一个小写英文字母。如果可能的话,找出需要进行的最少更改次数 S 一级-K 回文。
约束
- K 是一个整数。
- 0 ≤ K ≤ 5 \times 10^5
- S 由小写英文字母组成。
- 1 ≤ |S| ≤ 5 \times 10^5
输入
输入由标准输入按以下格式给出:
K S
输出
如果有可能获得精确的水平-K 回文,打印所需的最少更改次数。
如果不可能,则打印 impossible.
示例输入 1
4 aabaaaabaa
示例输出 1
0
我们可以找到的级别 aabaaaabaa 如下:
- 空字符串是一个级别-0 回文;
a是(空字符串)的串联,a,(空字符串)按此顺序,所以它是一个级别-1 回文;aa是一个串联a,a按照这个顺序,所以是一个级别——2 回文;aabaa是一个串联aa,b,aa按照这个顺序,所以是一个级别——3 回文;aabaaaabaa是一个串联aabaa,aabaa按照这个顺序,所以是一个级别——4 回文。
因此, aabaaaabaa 已经是一个级别了-4 回文,无需更改。
示例输入 2
2 aabaaaabaa
示例输出 2
4
例如,我们可以更改 aabaaaabaa to acbcaacbca 获得等级-2 回文。
请注意 aabaaaabaa 不是一个级别-2 回文。
示例输入 3
3 aabaaaabaa
示例输出 3
impossible
示例输入 4
5 aabaaaabaa
示例输出 4
impossible
示例输入 5
2 acaabcbababaaac
示例输出 5
6