给一个线性做法。

我们依次计算每个字符的最小值，采用双指针维护。

具体的，记当前字符为 $c$，维护两个指针 $l,r$，表示第 $l$ 个 $c$ 到第 $r$ 个 $c$ 能否全部并到一起。若可以就 $r$ 右移，否则 $l$ 右移。

问题转化为将区间 $[l,r]$ 全部并到一起的最小代价。注意到最优方案中一定有一个点不动，它两侧的点向它靠拢，我们再维护一个指针 $mid$ 表示这个点，那么当前代价为

$$\sum_{i=l}^{mid-1}{[(p_{mid}-mid+i)-p_i]}+\sum_{i=mid+1}^r{[p_i-(p_{mid}+i-mid)]}$$

$$=\sum_{i=l}^{mid-1}{(p_i-i)}-\sum_{i=mid+1}^{r}{(p_i-i)}-(r-mid)(p_{mid}-mid)+(mid-l)(p_{mid}-mid)$$

其中 $p_i$ 表示第 $i$ 个 $c$ 的下标。注意到我们预处理 $p_i-i$ 的前缀和即可 $O(1)$ 算出这个式子。

注意到这个式子关于 $mid$ 是下凸的，当 $l$ 和 $r$ 右移时，最优的 $mid$ 也是单调右移的，我们在双指针的同时维护 $mid$ 即可。

由于三个指针都单调右移，时间复杂度为 $O(L)$。