思路

• 关键观察：

  • 操作会改动四个位置，最靠左的改动是 $p=i-k$。若能让 $s_q$（其中 $q=i$）移动到 $p$ 且 $s_q<s_p$，则新串在位置 $p$ 就已更优，之后怎么改都不会更差。
  • 为使第二次交换尽量不影响前缀字典序，令 $j=n-k$（把第二次交换推到最右，交换 $(n-k,n)$）。

• 两种获益方式：

  1. 把更小的字符左移到更早位置：对每个 $p$，可选 $q\in[p+1,\ \lfloor\frac{n+p-1}{2}\rfloor]$ 且 $k=q-p$。若区间内存在 $s_q<s_p$，取最早的 $p$ 与使 $s_q$ 最小的 $q$，再取 $j=n-k$ 执行，答案最优。

题目内容

为了提升小红书笔记标签的可读性，我们计划对标签字符串进行一次双向字符置换操作，以获得更小的字典序结果。

具体地，给定一个长度为 $n$ 的字符串 $s$ (下标从 $1$ 开始)，你可以进行多一次如下作：

• 选取三个整数 $(i,j,k)$ ，满足 $1≤i≤j≤n，1≤i-k，j+k≤n$ 且 $k>0$ ;