Same Difference

The operation is:

Choose some $i$ with $1 \le i < n$, then set $s_i := s_{i+1}$.

So information only moves left. A character can copy the character immediately to its right. Nothing ever copies left-to-right.

The key forced fact

The last character $s_n$ can never be changed, because the operation only lets us choose indices $1$ through $n-1$.

That means the final string, if all characters are equal, must be:

$$s_n s_n s_n \dots s_n$$

There is no choice here. If you thought we were picking the most frequent character or doing some greedy “best target” thing, nope. The last character is the boss. Very democratic, obviously.

Lower bound

Look at any position $i$ where:

$$s_i \ne s_n$$

In the final string, this position must become $s_n$, so it must be changed at least once.

Each operation changes exactly one position. Therefore, the answer is at least the number of characters not equal to $s_n$.

Let that count be $cnt$.

So:

$$\text{answer} \ge cnt$$

Can we always do it in exactly that many operations?

Yes.

We can propagate copies of $s_n$ leftward. Start from the right side and move left. Whenever a character is not already equal to $s_n$, change it by copying from the right after the right side has already been made good.

More intuitively: every bad character needs one bonk, and one bonk is enough. Characters that are already equal to $s_n$ need zero operations.

So:

$$\text{answer} = \#\{i : s_i \ne s_n\}$$

Example

For abcabc, the last character is c.

Characters not equal to c are:

• a
• b
• a
• b

There are $4$, so the answer is $4$.

Algorithm

For each test case:

1. Read $n$ and $s$.
2. Let target = s[n - 1].
3. Count how many characters in s are not equal to target.
4. Print that count.

Complexity

For each test case, we scan the string once.

$$O(n)$$

The constraints are tiny, so this is extremely chill.