题解

思路

对一个区间和当前目标字符 $c$，定义要求给出两种对称选择：左半全部为 $c$、右半递归成为 $(c+1)$-good，或反过来。两种方案分别计算修改次数并取较小值。

为了避免在每层反复扫描半区，预处理 26 种字符的前缀出现次数，使任意区间内某字符数量可常数时间取得。

做法

递归函数处理区间 $[l,r)$ 与字符 $c$：

• 长度为 $1$ 时，返回该字符是否不等于 $c$；
• 计算左半改成 $c$ 的失配数，加上右半递归为 $c+1$ 的代价；
• 计算右半改成 $c$ 的失配数，加上左半递归为 $c+1$ 的代价；
• 返回两者较小值。

从整个字符串和字符 a 开始递归。

正确性证明

长度为 $1$ 时，唯一合法目标就是字符 $c$，返回值显然最优。对更长区间，定义规定所有合法 $c$-good 字符串必且只可能属于两个方向之一。算法在每个方向中准确计算固定半区的汉明修改数，并由归纳假设得到递归半区变为 $(c+1)$-good 的最少修改数。两部分位置不相交，代价可相加；再取两个完整方向的较小值，正是该区间的全局最优值。由归纳法结论成立。

复杂度分析

前缀频率预处理为 $O(26n)$。递归树有 $O(n)$ 个节点，每个节点常数查询，时间复杂度为 $O(n)$，空间复杂度为 $O(26n)$。

子任务说明

• $n\le64$ 时枚举全部合法目标字符串。
• $n\le4096$ 时在每个递归节点直接扫描半区，复杂度为 $O(n\log n)$。
• 满数据使用字符前缀频率优化为线性递归。