Palindrome Reorder
Given a string, the task is to rearrange the letters in such a way that the string becomes a palindrome.
Example: AAAABB
After rearranging, the string becomes: AABBAA
Observe that there are four ‘A’s and two ‘B’s in the original string.
The length of the string is six.
Imagine the string being divided into two halves:
AAB + BAA
Clearly the the right half is a inverted version of the left half.
That means, the frequency of each letter in both the halves is equal.
The left half has two ‘A’s and one ‘B’, and so does the right half.
Number of ‘A’s in left half = Number of ‘A’s in right half
Number of ‘B’s in left half = Number of ‘B’s in right half
Total number of ‘A’s = 2 * (Number of ‘A’s in left half)
Total number of ‘B’s = 2 * (Number of ‘B’s in left half)
Therefore, for a string to be converted into a palindrome, the frequency of each letter must be an even number.
Consider the string: AAAABCB
Observe that the length of this string is odd. Can it be converted into a palindrome?
Yes.
After rearranging, the string becomes: AABCBAA
Can this string be divided into two equal halves?
No.
But, if we separate the letter ‘C’, we can get two parts that are inversions of one another.
AAB + C + BAA
It can be observed that the frequencies of ‘A’ and ‘B’ are even.
But there is an extra letter with an odd frequency of one.
We conclude that a string can be converted into a palindrome, if the frequencies of all its letters is even or the frequency of all, except one, of its letters is even.
What if the string has two letters with odd frequencies?
String: AAAABBCDDD
Can this be rearranged to get a palindrome?
Let us try.
We put half of ‘A’s on left side and half on right side. Similarly, we put half of ‘B’s on left and the other half on right.
AAB + BAA
There are three ‘D’s. We append one ‘D’ at the end of the left half and one in the front of the right half.
AABD + DBAA
Now, we are left with a ‘C’ and a ‘D’.
Can these two letters be put in the answer string in such a way that we get a palindrome?
No.
Had we been left only with a ‘D’ or only with a ‘C’, we could have formed a palindrome string like this:
AABD + C + DBAA
or
AABD + D + DBAA
It is hence proved that a string can only be converted into a palindrome if the frequencies of each of its letters in an even number. Or if the frequency of only one letter is odd and that of the rest of the letters is even.
Let us see an example.
String: AAAABB
We store the frequency of each letter. A hash map can be used to do so.
We get, f(‘A’)= 4, f(‘B’)=2. There is no letter with odd frequency. Hence the string can be converted into a palindrome.
Now, once we have confirmed that the given string can be converted into a palindrome, the next task is to actually rearrange the letters and form the palindrome.
We will create two empty strings ‘lefthalf’ and ‘righthalf’.
lefthalf = “”
righthalf = “”
We will iterate through each letter of the map one by one.
And in each iteration, we will create another empty string str. In ‘str’, we will insert the letter, (it’s frequency)/2 number of times. Then, we will append this string ‘str’ at the end of the string ‘firsthalf’ and at the beginning of the string ‘righthalf’.
letter in the map = ‘A’, frequency = 4
str = “AA”
lefthalf = lefthalf + str = “” + “AA” = “AA”
righthalf = str+ righthalf= “AA” + “” = “AA”
letter in the map = ‘B’, frequency = 2
str = “B”
lefthalf = lefthalf + str = “AA” + “B” = “AAB”
righthalf = str+ righthalf = “B” + “AA” = “BAA”
Once, all the letters in the map have been visited, we return the string lefthalf+righthalf, which is a palindrome.
lefthalf + righthalf = “AAB” + “BAA” = “AABBAA”
Let us see another example.
String: AAAABBDDD
We store the frequency of each letter in a hashmap. We get, f(‘A’)= 4, f(‘D’)=3, f(‘B’)=2.
There is only one letter with an odd frequency, hence the string can be converted into a palindrome. We store the letter with odd frequency in a variable called ‘odd_char’.
We will iterate through each letter of the map one by one. In each iteration, we will create another empty string str.
In ‘str’, we will insert the letter, (it’s frequency)/2 number of times.
Then, we will append this string ‘str’ at the end of the string ‘firsthalf’ and at the beginning of the string ‘righthalf’.
letter in the map = ‘A’, frequency = 4
str = “AA”
lefthalf = lefthalf + str = “” + “AA” = “AA”
righthalf = str+ righthalf= “AA” + “” = “AA”
letter in the map = ‘D’, frequency = 3
(frequency/2 = 3/2 = 1)
str = “D”
lefthalf = lefthalf + str = “AA” + “D” = “AAD”
righthalf = str+ righthalf = “D” + “AA” = “DAA”
letter in the map = ‘B’, frequency = 2
str = “B”
lefthalf = lefthalf + str = “AAD” + “B” = “AADB”
righthalf = str+ righthalf = “B” + “DAA” = “BDAA”
All the letters in the map have been visited. But there was one letter with an odd frequency and we had stored this letter in the variable ‘odd_char’.
Instead of returning lefthalf+righthalf, we return:
lefthalf + odd_char + righthalf .
lefthalf +odd_char+ righthalf = “AADB” + “D” +“BDAA” = “AADBDBDAA”, which is a palindrome.
