核心思路

本题要求将字符串分割成若干区间，每个区间可以重排成回文串，且最短区间长度尽可能大。

1. 回文串的字母重排条件

一个区间可以重排成回文串的充要条件是：

• 区间内最多只有一个字母出现奇数次

2. 奇偶性状态表示

使用26位二进制数表示字母出现次数的奇偶性：

• 第 $k$ 位为 $1$ 表示字母 'a'+k 出现奇数次
• 第 $k$ 位为 $0$ 表示字母 'a'+k 出现偶数次

设 $pref[i]$ 表示前 $i$ 个字符的奇偶状态，则区间 $[l, r]$ 的状态为：

区间合法的条件是：

3. 二分答案 + 可行性判断

二分框架：

• 在 $[1, n]$ 范围内二分最短长度 $L$
• 判断是否存在分割方案，使得所有区间长度 $\geq L$ 且都合法

可行性判断：

• 定义 $f[i]$ 表示前 $i$ 个字符能否合法分割
• 对于每个位置 $i$，检查所有可能的 $j$ 使得：
  • $f[j] = \text{true}$
  • $i - j \geq L$
  • $\text{popcount}(pref[i] \oplus pref[j]) \leq 1$
• 由于合法的 $pref[j]$ 只有 $27$ 种可能（当前状态或翻转1位），可以 $O(26)$ 判断

4. 状态压缩优化

直接使用 $2^{26}$ 大小的数组会超内存，因此：

• 对实际出现的前缀状态进行离散化
• 只存储出现过的状态，大大减少内存使用

算法流程

1. 计算前缀奇偶状态 $pref[0..n]$
2. 离散化所有前缀状态
3. 二分最短长度 $L$
4. 对每个 $L$，用动态规划判断可行性
5. 输出最优解并构造分割方案

复杂度分析

• 时间复杂度：$O(26n \log n)$
• 空间复杂度：$O(n)$

该算法通过状态压缩和离散化巧妙处理了大状态空间问题，利用二分答案和动态规划高效求解了最优化问题。