Problem link:
PREREQUISITES:
Adhoc,greedy
PROBLEM:
Given N pairs of letters where each letter is ‘a’ or ‘b’ , we need to concatenate some of the pairs and form a longest possible palindrome.If there are many possible palindromes , we need to print lexicographical minimum palindrome.Note that only possible combinations given in the input will be ‘aa’ , ‘ab’ , ‘ba’ and ‘bb’.
EXPLANATION:
Palindrome is a string that reads same forward and backward( eg. madam, racecar ).Here we need to make a longest palindrome with the help of given pairs only.Lets see how can we make such palindrome in different cases.
Let the total number of ‘aa’ - N(aa) , ‘bb’ - N(bb) , ‘ab’ - N(ab) and ‘ba’ - N(ba).
Lets understand this problem by using different cases and examples
Case 1:
Suppose N(aa) and N(bb) is even and N(ab)=N(ba).In this case we can keep half of the ‘aa’ pairs at the beginning of the result , half at the end of the result.Now we can keep all the ‘ab’ pairs after ‘aa’ pairs which are in the beginning of the result and ‘ba’ pairs before the ‘aa’ pairs which are at the end of the result.Now we are only left with ‘bb’ pairs . We can keep all of them in the middle of the result.
Suppose N(aa)=4 , N(bb)=2 , N(ab)=3 and N(ba)=3.
In this case , first we can put the aa pairs like this [ aa aa … aa aa ] . Then we can put ab and ba pairs like this [ aa aa ab ab ab … ba ba ba aa aa ].Now we are remaining with bb pairs.We can keep all of them in the middle of the string. [aa aa ab ab ab bb bb ba ba ba aa aa aa].
Case 2:
Suppose N(aa) is odd , N(bb) is even .
For example N(aa)=5 , N(bb)=2 , N(ab)=3 and N(ba)=3.
Note that in this example N(aa) is one higher than previous example.Rest all is same.
In this case , after putting 4 aa pairs as mentioned in the previous example , we will be left with one aa pair . We can put it in the middle of the result.Our resulting palindrome is [ aa aa ab ab ab bb aa bb ba ba ba aa aa aa ].
Case 3:
Suppose N(bb) is odd and N(aa) is even .For example N(aa)=4 , N(bb)=3 , N(ab)=3 and N(ba)=3.
Note that in this example N(bb) is one higher than N(bb) in Example 1.Rest all is same.
After building the result as mentioned in Example 1 , we will be left with one bb pair. We can keep it in the middle of the result.
[ aa aa ab ab ab bb bb bb ba ba ba aa aa aa ].
Case 4:
Suppose N(aa) and N(bb) both are odd.For example N(aa)=5 , N(bb)=3 , N(ab)=3 and N(ba)=3. In this case after building string as mentioned in Example 1 , we will be left with one aapair and one bbpair. We can ignore one bb pair and keep one aa pair in the middle of the result.We ignored the remaining bb pair as there is no way to include it in the string and build the lexicographical minimum palindrome. [ aa aa ab ab ab bb aa bb ba ba ba aa aa aa ].In all the four example we have assumed N(ab) and N(ba) are equal.If they are not equal , then we can use only min(N(ab), N(ba)) pairs of each ab and ba type and we have to ignore rest of them.
Case 5:
Suppose N(aa)=5 , N(bb)=3 , N(ab)= 5 , N(ba)=3 .
In this case we can use only 3 pairs of ab and ba each and ignore rest 2 ab pairs.
[ aa aa ab ab ab bb aa bb ba ba ba aa aa aa ].