← 返回题目列表

AtCoder · arc113_c

C. 字符串入侵

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给定的是一个字符串 S 长度 N。让 s_i 表示 i- 第一个字符 S。求下列操作可以完成的最大次数。

  • 选择三个连续的字符 S, 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

我们可以进行三次操作,如下:

  • 这样做 i=2,将字符串更改为 acccpt;
  • 这样做 i=3,将字符串更改为 acccct;
  • 这样做 i=4,将字符串更改为 accccc.

示例输入 2

atcoder

示例输出 2

0

示例输入 3

anerroroccurred

示例输出 3

16