Let's first solve the subtask where the first and the second half of the string are anagrams. It's never useful to swap two adjacent characters if they are the same, which is why the relative order of equal characters never changes. That's why we can pair up the ~i^\text{th}~ occurrence of some letter in the first half with the ~i^\text{th}~ occurrence of that letter in the second half, and in the end, these characters have to be in the same positions in their corresponding halves. In this way we obtain ~n~ pairs and the problem can be formulated as follows: given a sequence of ~2n~ numbers, where the first and the second half are both permutations of ~1, 2, \dots, n~, equate the halves using the minimum number of adjacent swaps.

We claim that it's optimal to make swaps only in the second half until we make it equal to the first half. To show this, denote by ~d(p, q)~ the minimum number of swaps to turn a permutation ~p~ into another permutation ~q~. Notice that for every permutation ~r~, we can get from ~p~ to ~q~ by first going from ~p~ to ~r~ and then from ~r~ to ~q~, so we conclude that ~d(p, r) + d(r, q) \ge d(p, q)~. In our case, ~r~ represents the final permutation which will be repeated in each half. We see that equality occurs for example for ~r = p~, which is what we wanted to show.

Without loss of generality, we can change the labels of the pairs so that the first half consists precisely of the numbers ~1, 2, \dots, n~, and the second half is some permutation. This is now a classic problem of sorting a permutation with the minimum number of swaps, which turns out to be the same as counting the number of inversions, i.e. number of pairs of indices ~i < j~ where ~q_i > q_j~. We can count the number of inversions in ~\mathcal O(n \log n)~ using a Fenwick tree. Alternatively, you can think of it as doing a greedy algorithm by first moving the number ~1~ in permutation ~q~ to the first position, then number ~2~ to the second position and so on. For more details and similar ideas see here.

For the whole solution, we must also at some point get the initial string to a state in which the first and the second half are anagrams. Having in mind the partition into ~n~ pairs, we know for each letter whether it should end up in the first or second half. In other words, we have ~n~ left characters and ~n~ right characters which have to end up in their respective halves. We can make all swaps between left and right characters before making any swaps between two left or two right characters, so it's optimal to first get each letter to the desired half, and then solve the problem as described above. It's easy to show that we should first move the first left character to the first position, then the second left character to the second position, and so on. The number of swaps needed to get a left character to its final position is equal to the number of right characters which are to the left of it. This can be calculated in ~\mathcal O(n)~, making the final complexity ~\mathcal O(n \log n)~.