I think Greedy solution will also work in O(n)
if b[i] and b[i+1] are pairs the continue otherwise swap b[i+1] with pair of b[i]. Use hashmap to get the curr position and pair of an element.
Proof: We assume that B[i] is in correct place(anyway one of them will be in correct place). Then we can swap the pair of B[i] with B[i-1] or B[i+1] but think for B…we will have only the option of swapping with B. swapping with b[i+1] will produce configuration (a,b) and swapping with b[i-1] will produce (b,a)…for B we can get only (a,b) configuration…to get (b,a) configuration we will have to first swap b with b and then swap pair of it with current b which is not optimal. Hence, swapping b[i] and b[i+1] is atleast as good as swapping b[i] and b[i-1]. Now since we assume B[i] is already is in correct position we have to swap b[i+1] with pair of b[i] resulting in swap++