The string given has even length. I want to pair elements so that all pairs have distinct elements. It is impossible to do so when count of any element exceeds n/2 where n is length of string. For the other case of max frequency of any character less than n/2, it seems it is always possible to pair them. I am not sure if this is too obvious or there is an easy explanation to this, but I came up with a rather long explanation:

Suppose I do make a combination where x pairs have identical elements. I would have in this case pairs like, some of pp, some of qq, some or rr and so on. I can always swap the right element of one of these with others, eg pq, qp, etc. This can always be done and in the end I might be left with some of only one type of identical pairs eg some of pp. These pairs cannot be more than n/2 since that would be first condition at the beginning. Thus, the other pairs that have a p in them can at-most be (n/2 — 2*x)/2, which means I will still have at-least (n/2 — (n/2 — 2*x)/2) = x pairs left that don't have a p in them, now I can swap the right p of all the top x elements with last x right elements, hence I have all distinct pairs.

Is there a simpler explanation to this?

(apologies for bad formatting, I have to work on that)