E - Level K Palindrome Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋くんは、すぬけくんに日頃の感謝を込めてレベル K の回文を送ることにしました。レベル L の回文 ( L は 0 以上の整数 ) は以下のように定義されます。

  • 文字列 s の左右を反転させたものを \mathrm{rev}(s) と表す。
  • 文字列 s は s = \mathrm{rev}(s) であるとき、回文という。
  • 空文字列と回文でない文字列はレベル 0 の回文である。
  • 任意の空でないレベル L - 1 の回文 t に対して、t, \mathrm{rev}(t) をこの順に繋げた文字列はレベル L の回文である。
  • 任意のレベル L - 1 の回文 t と任意の文字 c に対して、t, c, \mathrm{rev}(t) をこの順に繋げた文字列はレベル L の回文である。

いま、高橋くんは文字列 S を持っています。
S から 1 文字選んで別の英小文字に書き換えるということを 0 回以上繰り返すことで、S をちょうどレベル K の回文にすることができるか判定してください。また、できる場合は、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 を acbcaacbca に書き換えると、ちょうどレベル 2 の回文を作ることができます。

aabaaaabaa はレベル 2 の回文ではないことに注意してください。

入力例 3

3
aabaaaabaa

出力例 3

impossible

入力例 4

5
aabaaaabaa

出力例 4

impossible

入力例 5

2
acaabcbababaaac

出力例 5

6

Score : 500 points

Problem Statement

As a token of his gratitude, Takahashi has decided to give Snuke a level-K palindrome. A level-L palindrome, where L is a non-negative integer, is defined as follows:

  • Let \mathrm{rev}(s) denote the reversal of a string s.
  • A string s is said to be a palindrome when s = \mathrm{rev}(s).
  • The empty string and a string that is not a palindrome are level-0 palindromes.
  • For any non-empty level-(L-1) palindrome t, the concatenation of t, \mathrm{rev}(t) in this order is a level-L palindrome.
  • For any level-(L-1) palindrome t and any character c, the concatenation of t, c, \mathrm{rev}(t) in this order is a level-L palindrome.

Now, Takahashi has a string S. Determine whether it is possible to make S an exactly level-K palindrome by doing the following action zero or more times: choose a character in S and change it to another lowercase English letter. If it is possible, find the minimum number of changes needed to make S a level-K palindrome.

Constraints

  • K is an integer.
  • 0 ≤ K ≤ 5 \times 10^5
  • S consists of lowercase English letters.
  • 1 ≤ |S| ≤ 5 \times 10^5

Input

Input is given from Standard Input in the following format:

K
S

Output

If it is possible to get an exactly level-K palindrome, print the minimum number of changes needed. If it is impossible, print impossible.

Sample Input 1

4
aabaaaabaa

Sample Output 1

0

We can find the level of aabaaaabaa as follows:

  • the empty string is a level-0 palindrome;
  • a is a concatenation of (empty string), a, (empty string) in this order, so it is a level-1 palindrome;
  • aa is a concatenation of a, a in this order, so it is a level-2 palindrome;
  • aabaa is a concatenation of aa, b, aa in this order, so it is a level-3 palindrome;
  • aabaaaabaa is a concatenation of aabaa, aabaa in this order, so it is a level-4 palindrome.

Thus, aabaaaabaa is already a level-4 palindrome and needs no changes.

Sample Input 2

2
aabaaaabaa

Sample Output 2

4

We can, for example, change aabaaaabaa to acbcaacbca to get a level-2 palindrome.

Note that aabaaaabaa is not a level-2 palindrome.

Sample Input 3

3
aabaaaabaa

Sample Output 3

impossible

Sample Input 4

5
aabaaaabaa

Sample Output 4

impossible

Sample Input 5

2
acaabcbababaaac

Sample Output 5

6