题解

思路

从右向左扫描字符串，用 $cnt_c$ 表示当前已经处理的后缀中字符 $c$ 的数量。

做法

扫描到位置 $i$ 时先把 $S_i$ 计入后缀；若 $S_{i-1}=S_i=c$，这对相邻的 $c$ 可以不断向右扩张，把后缀中每个不是 $c$ 的字符各改一次，而原本就是 $c$ 的位置不需要操作，因此答案增加 $(N-i)-cnt_c$。扩张结束后，这段后缀全部变为 $c$，所以清空计数并令 $cnt_c=N-i$。从右向左采用这一操作不会影响更左侧尚未处理的位置，而当前后缀中每个非 $c$ 字符至多贡献一次、也都能依次被改成 $c$，故每一步都取得了该相邻字符对能贡献的最大操作数，累加结果即为全局最优。

答案可能达到平方量级，需要使用 $64$ 位整数。

复杂度

每次触发时只需重置 $26$ 个字母的计数，因此总时间复杂度为 $O(26N)=O(N)$，空间复杂度为 $O(26)=O(1)$。