googology氏による \(O(N)\) 解法の代筆です．

\(S_{[l,r)}\) で \(S\) の \(l\) 文字目から \(r-1\) 文字目までを抜き出した部分文字列を表すものとします．

\(S_{[l,r)}\) に \(n\) 個の Y が含まれているとし，これらを最小のswap回数（以下「コスト」と表記）で連続させることを考えます．このとき，左から \(\lfloor \frac{n}{2} \rfloor\) 番目の Y は動かないとしてよいです（公式解説の(3)に相当します）．よって各 Y のコストへの寄与は，\(n\) や左から \(\lfloor \frac{n}{2} \rfloor\) 番目の Y のindexなどの値から高速に求めることができます．

区間に対してコストには単調性があります．そこで，尺取り法を用いてこの値を考えることができます．具体的には．以下のような要領でこの問題に正答することができます．

今，\(S_{[l,r)}\) に含まれている Y を連続させるためのコストが求まっていて，特にその値が \(K\) 以下であるとする．また，\(S_{[l,r)}\) に含まれる Y の個数 \(n\) ，左から \(\lfloor \frac{n}{2} \rfloor\) 番目の Y のindexなども管理されているとする．

• \(S_r\) を追加する．\(S_r\) が Y であるならば，コストに \(S_r\) の寄与を加算する．\(\lfloor \frac{n}{2} \rfloor\) の値が変わることもあるため，その差分の更新も行うことに注意．
• コストが \(K\) より大きい間，次の操作を繰り返す．
  • \(S_l\) を削除する．\(S_l\) が Y であるならば，コストから \(S_l\) の寄与を減算する．先と同様，\(\lfloor \frac{n}{2} \rfloor\) の値が変わり得ることに注意．

計算量は \(O(N)\) です．

googology氏の提出例 (7ms)