C - 暗号変換と補正 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、長さ N の英小文字からなるメッセージ S を暗号化しようとしています。

暗号化では、各文字をその ASCII コード（整数値）として扱います。英小文字の ASCII コードは a が 97、b が 98、…、z が 122 です。

まず、整数 k（1 \le k < N）を選び、メッセージを先頭から k 文字の前半部分と、残りの N - k 文字の後半部分に分割します。

前半部分に含まれるすべての文字の ASCII コードのビットごとの排他的論理和（XOR）を X_L、後半部分に含まれるすべての文字の ASCII コードの XOR を X_R とします。すなわち、前半部分の文字の ASCII コードを s_1, s_2, \ldots, s_k としたとき X_L = s_1 \oplus s_2 \oplus \cdots \oplus s_k であり、後半部分についても同様です。ここで \oplus はビットごとの排他的論理和を表します。

分割後、次の変換を行います。

  • 前半部分の各文字の ASCII コード c を c \oplus X_R に置き換える。
  • 後半部分の各文字の ASCII コード c を c \oplus X_L に置き換える。

変換後に得られる N 個の整数値を順に A_1, A_2, \ldots, A_N とします。なお、A_i は 0 以上 127 以下の整数ですが、必ずしも英小文字の ASCII コードの範囲（97 以上 122 以下）に収まるとは限りません。

そこで高橋君は、補正列 D_1, D_2, \ldots, D_N を選び、各 i（1 \le i \le N）について最終的な暗号値を A_i + D_i とします。暗号文として有効であるためには、すべての最終値が英小文字の ASCII コードの範囲に収まる必要があります。

補正列 D は次の条件をすべて満たさなければなりません。

  • 各 D_i は非負整数である。
  • D_1 \ge D_2 \ge \cdots \ge D_N（単調非増加）である。
  • すべての i（1 \le i \le N）について、97 \le A_i + D_i \le 122 を満たす。

分割位置 k に対して、上記の条件をすべて満たす補正列 D が存在するとき、その k を良い分割位置と呼びます。

良い分割位置の個数を求めてください。

制約

  • 2 \leq N \leq 5000
  • S は長さ N の英小文字からなる文字列

入力

N
S
  • 1 行目には、メッセージの長さを表す整数 N が与えられる。
  • 2 行目には、長さ N の英小文字列 S が与えられる。

出力

良い分割位置の個数を整数として出力してください。

入力例 1

4
abcd

出力例 1

3

入力例 2

3
aaa

出力例 2

1

入力例 3

30
abcdefghijklmnopqrstuvwxyzabcd

出力例 3

1

入力例 4

100
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuv

出力例 4

4

入力例 5

2
az

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is trying to encrypt a message S consisting of lowercase English letters with length N.

In the encryption, each character is treated as its ASCII code (an integer value). The ASCII codes of lowercase English letters are 97 for a, 98 for b, …, 122 for z.

First, he chooses an integer k (1 \le k < N) and splits the message into the first half consisting of the first k characters and the second half consisting of the remaining N - k characters.

Let X_L be the bitwise exclusive OR (XOR) of the ASCII codes of all characters in the first half, and X_R be the XOR of the ASCII codes of all characters in the second half. That is, if the ASCII codes of the characters in the first half are s_1, s_2, \ldots, s_k, then X_L = s_1 \oplus s_2 \oplus \cdots \oplus s_k, and similarly for the second half. Here, \oplus denotes the bitwise exclusive OR.

After splitting, the following transformation is performed:

  • Replace the ASCII code c of each character in the first half with c \oplus X_R.
  • Replace the ASCII code c of each character in the second half with c \oplus X_L.

Let A_1, A_2, \ldots, A_N be the N integer values obtained after the transformation, in order. Note that each A_i is an integer between 0 and 127 inclusive, but does not necessarily fall within the ASCII code range of lowercase English letters (97 to 122 inclusive).

Therefore, Takahashi chooses a correction sequence D_1, D_2, \ldots, D_N, and for each i (1 \le i \le N), the final cipher value is A_i + D_i. For the ciphertext to be valid, all final values must fall within the ASCII code range of lowercase English letters.

The correction sequence D must satisfy all of the following conditions:

  • Each D_i is a non-negative integer.
  • D_1 \ge D_2 \ge \cdots \ge D_N (monotonically non-increasing).
  • For all i (1 \le i \le N), 97 \le A_i + D_i \le 122 is satisfied.

For a split position k, if there exists a correction sequence D satisfying all the above conditions, then k is called a good split position.

Find the number of good split positions.

Constraints

  • 2 \leq N \leq 5000
  • S is a string of lowercase English letters with length N

Input

N
S
  • The first line contains an integer N representing the length of the message.
  • The second line contains a string S of lowercase English letters with length N.

Output

Output the number of good split positions as an integer.

Sample Input 1

4
abcd

Sample Output 1

3

Sample Input 2

3
aaa

Sample Output 2

1

Sample Input 3

30
abcdefghijklmnopqrstuvwxyzabcd

Sample Output 3

1

Sample Input 4

100
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuv

Sample Output 4

4

Sample Input 5

2
az

Sample Output 5

1