この問題を\(O(N)\)で解く方法を示します。

---

次の w は、どのような操作を行っても "iwi" の中央になることがありません。

• ww のの一部になっている w
• 文字列の両端にある w

理由："iwi" では w の両隣が必ず i である必要があるため

したがって以下の操作は合計の操作回数に影響しません。

• ww を境界として文字列を分割する
• 文字列の両端の w を取り除く

上記の処理をすべて行った後、各部分文字列は必ず次の形になります。

\[\Large \underbrace{i \dots i}_{a_0} \, w \, \underbrace{i \dots i}_{a_1} \, w \, \dots \, w \, \underbrace{i \dots i}_{a_W}\]

ここで

• W：含まれる w の個数
• \(a_i ≥ 1 (i = 0, 1, ..., W)\)（ww がなく、両端が i であることから従う）
• I \(= a_0 + a_1 + ... + a_W\)：i の総数

です。

1 回の "iwi" を取り除く操作では、

• w を 1 個
• i を 2 個

消費します。

よって、操作回数の上界は\(min(W, \lfloor{\frac{I}{2}}{\rfloor})\)です。

以下の手順により、この上界が常に達成可能であることを示します。

\(a_j \geq 2\) または\(a_{j + 1} \geq 2\)を満たす \(j\) 番目の w を選んで操作すると、その w と両隣の i でiwiができます。

\(a_j + a_{j+1} - 2\geq1\) であるため、結合後の i の個数は 1 以上に保たれます。

この操作を可能な限り続けると、必ず次のいずれかの状態になります。

ケース 1：wが含まれない

• すべての w を使い切った
• 操作回数は \(W\)

ケース 2：すべての a_i = 1

• 文字列は iwiwi...iwi の形
• 左から貪欲に "iwi" を作ると、残る i は高々 1 個
• 操作回数は \(\lfloor{\frac{I}{2}}{\rfloor}\)

どちらの場合も、
答えの上界 \(min(W, \lfloor{\frac{I}{2}}{\rfloor})\) に一致します。

---

以上より、与えられた文字列を走査し、iの個数、wの個数をカウントしながら文字列を分解することで、計算量 \(O(N)\) を達成できました。