Why does this post have the "december cookoff" tag? isn't that tag supposed to be on a codechef round announcement?

Let the substring be $$$s_1s_2s_3\ldots s_m$$$ of length $$$m$$$. We want to make the number of indices $$$2 \le i \le m$$$ where $$$s_i \neq s_{i - 1}$$$ zero (call these bad indices).

In one move, we can reduce the number of these indices by at most $$$2$$$, since an operation will not change the number of bad indices within a substring. Also, a substring has at most two neighbors (to the left and the right) that it can merge with. Therefore, if there are $$$x$$$ bad indices, the minimum number of moves it needed to clear out all the bad indices is $$$\lceil \frac{x}{2} \rceil$$$.

Let's consider the types of bad indices. We can split them into two types:

1. $$$s_i = s_{i - 1} + 1 \bmod 3$$$ (for example, AB, BC, CA)
2. $$$s_i = s_{i - 1} - 1 \bmod 3$$$ (for example, AC, CB, BA)

Note that if we have two bad indices of different types, we can use them to reduce the number of bad indices by $$$2$$$. For example:

• If we have AB.....CB, we can change it to A[A......B]B by selecting the middle substring and applying the permutation A, C, B.
• If we have AB.....BA, we can change it to A[A......A]A by selecting the middle substring and applying the permutation B, A, C (note that C, A, B would also work).

The other cases can be shown to work in the same way.

Also note that if we apply one of the permutations A, C, B, B, A, C, or C, B, A to some substring, all the bad indices in the substring will get their types flipped.

Using these two kinds of moves, we can do the following: while there is at least one bad index of both type 1 and 2, we can remove one of each in a single move. Eventually, there will only be $$$y$$$ bad indices of a single type.

Suppose WLOG that this remaining type is type 1, and that the resulting string has the form ABCABCABCABC.... Then, let's pick the middle bad index and apply one of the permutations A, C, B, B, A, C, or C, B, A to the last half of the bad indices. If we pick which one to apply correctly, we can reduce the number of bad indices by 1 and flip the type of the last half of the indices. For instance, if we have ABCA...BC[ABC...CABC] and we want to flip the latter half, we can choose the permutation C, B, A to get ABCA...BC[CBA...ACBA].

Now, if we flip the latter half, we can keep removing two at a time until we get to zero. This solution is optimal for odd $$$x$$$, since it achieves $$$\lceil \frac{x}{2} \rceil$$$ operations (the minimum possible). However, for even $$$x$$$, it's possible that this solution will take $$$\frac{x}{2} + 1$$$ operations: which is worse than the $$$\frac{x}{2}$$$ minimum possible.

How can we tell if $$$\frac{x}{2}$$$ is achievable? Note that we can also apply operations on strings of the form A[B.....A]B -> A[A....B]B. If our string only has bad indices of type 1, a little math will show that we can only apply this operation to substrings [B...A] of length $$$y$$$ such that $$$y \equiv 1 \bmod 3$$$. A little more math, and we can see that using this operation, we can remove any multiple of $$$6$$$ bad indices of the same type at a time (e.g. using $$$y = 4$$$, [1111]11 -> 2211 -> 2[21]1 -> [21] -> empty). So, if the string had $$$t_1$$$ and $$$t_2$$$ bad indices of each type at the start, and $$$t_1 + t_2$$$ is even, the answer will be $$$\frac{t_1 + t_2}{2}$$$ (the minimum achievable) if $$$|t_1 - t_2| \equiv 0 \bmod 6$$$.

It turns out that not only is this a sufficient condition, it is also necessary. If you work out the cases, you'll find that any operations that removes $$$2$$$ bad indices does not change the value of $$$|t_1 - t_2| \equiv 0 \bmod 6$$$ (you only need to check $$$4$$$ cases where the first bad index is AB, the other cases are symmetric).

So, if $$$t_1 + t_2$$$ is odd, then the answer is $$$\lceil \frac{t_1 + t_2}{2} \rceil$$$. Otherwise, the answer will be $$$\frac{t_1 + t_2}{2}$$$ if $$$|t_1 - t_2| \equiv 0 \bmod 6$$$, and $$$\frac{t_1 + t_2}{2} + 1$$$ otherwise.