SCCPC2026 D 那一天的回文字符串 题解
题目链接：QOJ Contest 3789 Problem D
这题的操作看起来是在“重排字符串”，但真正不变的是每个位置的奇偶性：奇数下标上的字符永远只能留在奇数下标集合里，偶数下标上的字符也一样。
因此我们不需要关心字符的具体位置，只需要分别统计两类位置中每个字母出现了多少次。
记：
$$
cnt_1(c)=c\text{ 在奇数下标中出现的次数},\qquad
cnt_0(c)=c\text{ 在偶数下标中出现的次数}.
$$
接下来只要看回文串中一对对称位置 $i$ 和 $n+1-i$ 的奇偶性。
如果 $n$ 是偶数，那么 $i$ 和 $n+1-i$ 的奇偶性一定不同。也就是说，每一对相等字符都必须由一个奇数下标位置和一个偶数下标位置提供。所以对每个字母 $c$，必须有
$$
cnt_0(c)=cnt_1(c).
$$
如果 $n$ 是奇数，那么 $i$ 和 $n+1-i$ 的奇偶性一定相同。中心位置是奇数下标，因此：
- 偶数下标中的字符必须全部两两配对；
- 奇数下标中的字符允许有一个字母剩下来放在中心。
也就是要求
$$
#{c\mid cnt_0(c)\text{ 为奇数}}=0,
$$
并且
$$
#{c\mid cnt_1(c)\text{ 为奇数}}\le 1.
$$
满足对应条件就输出 YES，否则输出 NO。
复杂度为 $O(|s|)$。