String Invasion

AtCoder

IDarc113_c

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

accept

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`.

Input #2

atcoder

Output #2

Input #3

anerroroccurred

Output #3

API Response (JSON)

{
  "problem": {
    "name": "String Invasion",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc113_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\n*   Choose three consecutive characters in $S...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments