Let a block be a part consisting of two or more consecutive same letters. Also, let us call a block essential when it is the first block in \(S\) or consists of a letter different from that of the previous block. For example, the string abbbcbbccca has two essential blocks: one composed of the \(2\)-nd, \(3\)-rd, \(4\)-th characters b and another composed of the \(8\)-th, \(9\)-th, \(10\)-th characters c. The block composed of the \(6\)-th, \(7\)-th characters b is not essential since there is another block consisting of b just before it.

Now, consider the sequence of operations below. For an essential block \(B\), let the first and last characters of \(B\) be the \(l(B)\)-th and \(r(B)\)-th characters of \(S\).

• If there is no essential block \(B\) such that \(r(B)\neq |S|\), terminate.
• If there is such a block, do the operation on the \((r(B)-1)\)-th, \(r(B)\)-th, \((r(B)+1)\)-th characters of \(B\).

Let us prove that this sequence achieves the maximum number of operations possible. For each essential block \(B\), we define its potential \(\phi(B)\) as the sum of the following, where \(B'\) is the essential block that appears just after \(B\).

• The number of characters different from the letter in \(B\) among the sequence composed of the \((r(B)+1)\)-th, \(\dots\), \((l(B')-1)\)-th characters of \(S\).
• The number of characters in the sequence composed of the \(l(B')\)-th, \(\dots\), \(|S|\)-th characters of \(S\): \(|S|-l(B')+1\).

The potential of the string \(S\), \(\phi(S)\), is defined as the sum of potentials \(\phi(B)\) over all essential blocks \(B\).

Now, from the definition, we can see that every operation decreases \(\phi(S)\) by at least \(1\). On the other hand, we can also see that every operation in the above sequence decreases \(\phi(S)\) by exactly \(1\), and \(\phi(S)=0\) in the end. Thus, this sequence achieves the maximum number of operations possible. Since we can find \(\phi(S)\) in linear time, we can now solve the problem in linear time.