思路

把原串字符放在偶数坐标，把相邻字符之间的间隙放在奇数坐标。每个给定回文会产生两类约束：回文内部关于中心对称的字符必须相等；若回文没有碰到边界，紧邻回文两端的两个字符必须不等，否则最长回文还可以继续扩展。

做法

用并查集维护所有必须相等的位置，并在并查集连通块之间记录必须不等的边。得到约束图后，从左到右处理原串位置。某个连通块第一次出现时，选择与已经着色的相邻块都不同的最小字母。后续属于同一连通块的位置直接使用已经确定的字母。由于输入保证有解，这一过程一定能在二十六个小写字母内完成；从左到右每次取最小可行字符也直接保证了字典序最小。

直接枚举每个回文内部的对称位置会达到平方复杂度。满分做法复用 Manacher 算法的镜像信息：维护当前覆盖最右位置的已处理回文。处理新中心时，镜像中心已经确认的那一段相等关系无需再次扫描，只从尚未覆盖的位置继续合并。最右端点只会单调右移，因此所有新扩展的总次数是线性的。不等关系每个中心至多加入一条。

正确性证明

每次新扩展都合并一对处于给定最长回文内部的对称字符，所以并查集中的任意两个位置都被输入强制相等。每个未触及边界的最长回文外侧一对字符被连为不等边；若二者相等，该回文就能继续扩展，与“最长”矛盾。反过来，回文内部全部相等且外侧在存在时不等，恰好保证每个输入半径既能达到又不能继续增加，因此约束与输入等价。

着色时，同一并查集连通块统一取一个字符，并避开所有已经着色的不等邻块，所以最终字符串满足全部相等与不等约束。对尚未着色的邻块，其之后着色时会避开当前颜色，故所有不等边最终都被满足。

按原串位置从左向右看，一个连通块第一次出现时，算法选择所有不与已确定前缀冲突的字符中的最小者。未处理位置不能改变已经确定的约束。因此任何其他合法字符串在第一个与答案不同的位置都不能取更小字符，所得字符串即为字典序最小解。

复杂度分析

逆向 Manacher 扩展总次数为 $O(N)$，并查集操作的均摊复杂度为 $O(\alpha(N))$。时间复杂度为 $O(N\alpha(N)+26N)$，空间复杂度为 $O(N)$。