Subtask 1

Let us designate an arbitrary index ~i~ as our 'split point'. Let ~C_x~ be the number of characters of type "x" in the input string. Now let us say that in the final configuration, ~i~ is the first position with As. Then the range ~[i, i + C_A)~ must all be As in the final configuration, and we call it the 'A section'.

This means that we need to do only as many moves as there are Bs in the A section. Since there are no Cs, we only need to swap any Bs in the A section with As in the B section, and since they correspond 1 to 1, that is our answer.

For the first subtask, we brute force all values of ~i~ and count the number of Bs trivially, then take the lowest number of moves.

Time Complexity: ~\mathcal O(N^2)~

Subtask 2

For the second subtask, we count the number of Bs using a Prefix Sum Array. Let ~P_B \text{ at } j~ be the number of Bs in the prefix of length ~j~. Then we can use this to count the number of Bs in the A section in ~\mathcal O(1)~ time.

Time Complexity: ~\mathcal O(N)~

Subtask 3

For this subtask, we have to consider Cs. We take a different approach.

We go through all of the permutations of ABC. Without loss of generality, assume our permutation is ABC. The other 5 cases are analogous. Then we let the first ~i~ characters of our final configuration be A. We can brute force through all possible values of ~i~ from ~0~ to ~C_A~. Then we know the exact state of our final configuration. The A section now forms both a suffix and a prefix of the string, but it is still the same section and we will process it that way.

We now simulate the swaps. For each element in the A section that is not an A, we swap it with an A in the corresponding section if we can. If we cannot, we can swap it with a random A from the other section. We do the same for the B section, and we have our answer.

For this solution, we have to keep track of the positions of each letter in each section. We can do this with 3 vectors for the B and C sections, for 6 vectors total.

Time Complexity: ~\mathcal O(N^2)~

Full Solution

For full marks, we build on the solution from the second subtask.

Let ~N_x~ be the number of non-x characters in the x section, and let ~S_{x,y}~ be the number of type y characters in the x section.

Note that now for any index ~i~, we still have the A section from ~[i, i + C_A)~. However, we need to consider that the next section can be either B or C. We can simply try both for all values of ~i~. Without loss of generality, assume the next section is B.

Then the B section is from ~[i + C_A, i + C_A + C_B)~.

In this case, we must move all non-As from the A section and all non-Bs from the B section. However, note that we can save moves by swapping As in the B section with Bs from the A section. Thus, our answer for a given value of ~i~ is:

$$\displaystyle N_A + N_B - \min(S_{A,B}, S_{B,A})$$

We can use a PSA to compute the ~S~ and ~N~ values in ~\mathcal O(1)~ time. We can then brute force all values of ~i~ and consider both A section followed by B section or A followed by C.

Time Complexity: ~\mathcal O(N)~