配点 : $500$ 点

問題文

長さ $N$ の文字列 $S$ が与えられます。$S$ の $i$ 文字目を $s_i$ で表します。以下の操作を繰り返せる回数の最大値を求めてください。

• 連続する $3$ 文字 $s_i,s_{i+1},s_{i+2}\quad (1\leq i\leq |S|-2)$ であって、$s_i=s_{i+1}\neq s_{i+2}$ であるものを選ぶ。$s_{i+2}$ を $s_i$ で置き換える。

制約

• $3 \leq |S| \leq 2\times 10^5$
• $S$ は英小文字からなる

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

操作を繰り返せる回数の最大値を出力せよ。

accept

3

以下のように $3$ 回の操作を行うことができます。

• $i=2$ に対して操作を行う。操作後の文字列は acccpt になる。
• $i=3$ に対して操作を行う。操作後の文字列は acccct になる。
• $i=4$ に対して操作を行う。操作後の文字列は accccc になる。

atcoder

0

anerroroccurred

16