A and B

We need the minimum adjacent swaps so that all copies of either a or b form one continuous block.

The trap here is thinking we need to decide the whole final string. We don't. If we choose to group all as, then the bs are just filler around that block. Same for grouping all bs. So solve this smaller problem:

Given the positions of one character, what is the minimum adjacent swaps needed to move all of them into consecutive positions?

Then do it for a, do it for b, and take the minimum.

Grouping One Character

Suppose we are grouping some character c, and it appears $k$ times at 0-indexed positions:

$p_0 < p_1 < \dots < p_{k-1}$

In the final string, these $k$ characters must occupy some consecutive block:

$x, x+1, x+2, \dots, x+k-1$

The first occurrence goes to $x$, the second to $x+1$, and so on.

Why can we assume that order? Because equal characters do not need to cross each other. If two as swap places, the string doesn't become more useful; it is just wasting swaps. So the optimal matching preserves order.

For a fixed block start $x$, the number of adjacent swaps needed is:

$\sum_{i=0}^{k-1} |p_i - (x+i)|$

Each chosen character must move that many positions, and adjacent swaps exactly measure total movement across other characters.

Now simplify the expression:

$|p_i - (x+i)| = |(p_i-i)-x|$

So the cost becomes:

$\sum_{i=0}^{k-1} |(p_i-i)-x|$

Let:

$q_i = p_i - i$

Now the problem is:

Pick an integer $x$ minimizing $\sum |q_i-x|$.

Classic median moment. The value minimizing sum of absolute distances is any median of the array.

So the optimal cost for this character is:

$\sum_{i=0}^{k-1} |q_i - \text{median}(q)|$

That is the whole problem. No DP, no graph nonsense, no cursed string simulation.

Why This Works

Adjacent swaps can be viewed as moving selected characters left or right through the other character. If an occurrence moves from position $p_i$ to target position $t_i$, it contributes $|p_i-t_i|$ swaps.

Since the selected characters are identical, preserving their order is always optimal. Therefore, choosing a final consecutive block completely determines the target position of each occurrence.

The only remaining freedom is the block start $x$. After subtracting $i$ from each original position, the targets all collapse to the same unknown $x$, and minimizing absolute deviations gives the median.

Algorithm

For each test case:

1. Collect positions of a.
2. Compute the grouping cost for those positions.
3. Collect positions of b.
4. Compute the grouping cost for those positions.
5. Output the minimum.

For a position list pos:

• If its size is $0$ or $1$, cost is $0$.
• Build conceptually $q_i = pos[i] - i$.
• Let $m = q_{k/2}$.
• Return $\sum |q_i-m|$.

The adjusted array is already nondecreasing because positions strictly increase, so no sorting is needed.

Complexity

Each test case is processed in $O(n)$ time.

Across all tests, the total complexity is:

$O\left(\sum n\right)$

Memory usage is $O(n)$ for the stored positions. Costs can be up to about $n^2$, so use long long.