题解

思路

若 $S$ 全为 d，任何非空操作都会在最早改变的位置产生 p，所以不操作最优。

做法

否则设 $l$ 为最左侧 p。左端点在 $l$ 右侧的操作无法改善第 $l$ 位；左端点在 $l$ 左侧时，第一次发生变化的位置原本是 d，也不会优于从 $l$ 开始把该位变成 d 的某个操作。因此最优非空操作一定可以取左端点 $l$。

枚举右端点 $r=l,l+1,\ldots,N$，显式生成把 $S[l..r]$ 逆序并翻转 d/p 后的候选串，与原串一起取字典序最小值即可。

复杂度

共有 $O(N)$ 个候选，每个候选构造与比较需要 $O(N)$ 时间，总时间复杂度为 $O(N^2)$，空间复杂度为 $O(N)$。