String Rotation Game

Treat the string as circular first. Rotation does not reshuffle characters; it only chooses which circular edge gets cut to become the gap between the end and the beginning of the final string.

In any ordinary linear string, the number of blocks is

$$1 + \#\{i : 1 \le i < n,\ s_i \ne s_{i+1}\}.$$

Every time two consecutive characters differ, a new block starts. Equal neighbors stay inside the same block. That's the whole game; no hidden dragon here.

Now put the string on a circle and count

$$c = \#\{i : 0 \le i < n,\ s_i \ne s_{(i+1) \bmod n}\}.$$

These are the circular block boundaries. When we rotate the string, we choose one circular edge to cut. The final linear string contains the other $n-1$ edges as adjacent pairs.

There are two cases:

• If we cut an edge whose characters are different, then we remove one boundary. The score is $1 + (c-1) = c$.
• If we cut an edge whose characters are equal, then no boundary is removed. The score is $1 + c$.

So we obviously prefer cutting between equal characters, if such an edge exists.

If at least one circular adjacent pair is equal, the answer is $c+1$. If every circular adjacent pair is different, then $c=n$, and every cut removes one boundary, so the score is $n$. This is also captured by the compact formula

$$\boxed{\min(n, c+1)}.$$

Why does this prove optimality? A rotation is exactly one cut in the circular string. For any chosen cut, the internal adjacent pairs are fixed: all circular edges except the cut edge. The score is always one plus the number of different internal edges. Therefore the only choice that matters is whether the cut edge itself was a boundary. Cutting a non-boundary is best when possible; otherwise all edges are boundaries and the score cannot exceed $n$ anyway.

Edge cases:

• $n=1$: there are no useful boundaries, $c=0$, answer $1$.
• All characters equal: $c=0$, answer $1$.
• Alternating or all-distinct around the circle with every neighbor different: $c=n$, answer $n$.

Complexity is $O(n)$ per test case and $O(1)$ extra memory besides the string.