分割位置 \(k\) を全探索することを考えます。

\(k\) を固定した際、変換により得られる \(A_1,A_2,\ldots,A_N\) に対し以下の問題が解ければ良いです。

• 以下の条件を全て満たす正整数列 \(D=(D_1,D_2,\ldots,D_N)\) は存在するか？
  • \(D_1 \geq D_2 \geq \ldots \geq D_N \geq 0\)
  • \(97 \le A_i + D_i \le 122\)

これは \(D_1\) から順に値を決めていくことで判定ができます。\(D_{i+1}\) の条件を考えると \(D_i\) は可能な範囲で最大のものを取れば良いです。したがって、\(D_i=\max(122-A_i,D_{i-1})\) として \(D\) を決めていき、条件を満たすような \(D\) が構成できるか判定すれば良いです。

実装例(Python3)

n = int(input())
a = [ord(c) for c in input()]
ans = 0
for k in range(1, n):
    b = a[:k]
    c = a[k:]
    xl, xr = 0, 0
    for x in b: xl ^= x
    for x in c: xr ^= x
    now = 127
    for v in [xr ^ x for x in b] + [xl ^ x for x in c]:
        l, r = 97 - v, 122 - v
        if r < 0:
            break
        now = min(now, r)
        if now < l:
            break
    else:
        ans += 1
print(ans)