[R28E]最多好串 - 代码源竞赛平台

时空限制

1S/512M

题目描述

一个由小写字母构成的字符串 $s$ 是“好的”，需要满足以下两个条件：

1. $s$ 的长度必须是偶数（不妨设 $|s| = 2k$）。
2. 将字符串平分为前后两半（前 $k$ 个字符为前半部分，后 $k$ 个字符为后半部分），这两部分拥有完全相同的字符构成（即每种字符的出现次数相同）。

例如：

• aabbbbaa 是一个好的字符串。它的长度为 $8$，前半部分 aabb 和后半部分 bbaa 都含有两个 a 和两个 b。
• abacabac 也是一个好的字符串。它的长度为 $8$，前半部分 abac 和后半部分 abac 字符数量完全相同。
• abacaba 不是好的字符串，因为它的长度是奇数。
• abcaab 不是好的字符串。它的长度为 $6$，前半部分 abc 中 c 出现 $1$ 次，而后半部分 aab 中 c 出现 $0$ 次。

现给定一个长度为 $n$ 的字符串 $S$。对于每个位置 $i$（从 $1$ 到 $n$），考虑以下操作：将 $S[i]$ 替换为任意一个小写字母（共 $26$ 种选择，包括自身）。对于每种替换，可得到一个新字符串，并统计该字符串中“好的”子串的数量。定义 $f(i)$ 为所有 $26$ 种替换中，能得到的最大“好的”子串数量。

请计算 $f(1), f(2), \dots, f(n)$ 的值。

格式

输入格式

第一行包含一个整数 $n$，表示字符串 $S$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $S$。

输出格式

输出一行，包含 $n$ 个用空格隔开的整数，分别代表 $f(1), f(2), \dots, f(n)$。

样例

样例输入 #1

4
zzza

样例输出 #1

2 2 2 4

数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 60$。

对于 $100\%$ 的数据，$1 \leq n \leq 1000$，字符串 $S$ 仅包含小写英文字母。