Solution:
We first take all the characters c with even number of occurences.
We arrange them as follows.
ccc.... ccc....
Now, we take two characters c, d such that c and d both have odd number of occurrences.
We arrange them as follows.
cc..ccdd..dd cc..cccdd..d
Note that number of characters with odd number of occurences will be even as total number of characters are even, so they can always be grouped as above.
Proof:
We have a grid of 2 * n. Suppose we have to only fill it by characters equal to c.
For a character c, the maximum number of edges will be achieved when the characters form a consecutive block.
For even number of characters
cc.... cc....
For odd number of characters
cc... cc..c
By using the above given pattern, we can get the maximum number of edges for a single character.
This fact can be proved as follows. Let us arrange the characters c in any way. We will prove that we can reach from that configuration to the current configuration by always increasing (can be equal too) the edges.
We can always rearrange the cells in such a way that the columns which contain at least one c are consecutive. This can be achieved by always increasing (can be equal too) the edges.
So, we rearrange the cells in this manner, i.e. we will get the following.
cccc.cc cc..c.c
Consider the left most column. If it contains two c’s, then that’s good (i.e. it is same as our pattern), we move to second column. So we reach the first column where there is a single c (e.g. second column in the above example)
Now, we find an empty cell where we can fit this c. In the column, where we move c will be containing at least one neighbouring c. So, by doing this, we can only increase the edges (they can be same too, but can’t decrease).
This way, we make this column empty. Now, we can again rearrange the columns in such a way that all the columns with c’s are consecutive without decreasing the number of edges.
We keep repeating this step untill there is a single column with exactly one c (odd case) or zero columns with exacly one c.
Now, if we can rearrange each block of equal characters in the grid in such a way that the above pattern is achievable for every block of equal characters, then that pattern will lead to overall maximum answer.
We can always do this in the following way.
We first take all the characters c with even number of occurences.
We arrange them as follows.
ccc.... ccc....
Now, we take two characters c, d such that c and d both have odd number of occurrences.
We arrange them as follows.
cc..ccdd..dd cc..cccdd..d
Note that number of characters with odd number of occurences will be even as total number of characters are even, so they can always be grouped as above.
Thus, we have achieved the desired pattern.
Time complexity of this approach will be \mathcal{O}(2 * n).