C - String Invasion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

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

入力例 1

accept

出力例 1

3

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

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

入力例 2

atcoder

出力例 2

0

入力例 3

anerroroccurred

出力例 3

16

Score : 500 points

Problem Statement

Given is a string S of length N. Let s_i denote the i-th character of S. Find the maximum number of times the following operation can be done.

  • Choose three consecutive characters in S, s_i,s_{i+1},s_{i+2}\quad (1\leq i\leq |S|-2), such that s_i=s_{i+1}\neq s_{i+2}, and replace s_{i+2} with s_i.

Constraints

  • 3 \leq |S| \leq 2\times 10^5
  • S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the maximum number of times the operation can be done.

Sample Input 1

accept

Sample Output 1

3

We can do the operation three times, as follows:

  • do it with i=2, changing the string to acccpt;
  • do it with i=3, changing the string to acccct;
  • do it with i=4, changing the string to accccc.

Sample Input 2

atcoder

Sample Output 2

0

Sample Input 3

anerroroccurred

Sample Output 3

16