All submissions for this problem are available.
Farzi Coder wants to give a nice Christmas present to his brother. For that he has brought N pairs of letters where each letter is either 'a' or 'b'. So, the possible pairs are "aa", "ab", "ba" or "bb". Now, Farzi Coder's brother loves palindromes. So, he decided to concatenate some of the pairs (possibly all or none) and form a palindrome. He wants the longest such palindrome possible. If there are multiple such longest palindromes possible, he wants to give his brother the lexicographically smallest palindrome among them as the gift. Since he is, well, Farzi Coder, you have to help him build the gift.
The first line of the input has the number T denoting the number of test cases.
The first line of each test case has the number N denoting the number of pairs in this case.
Each of the next N lines contain a pair of characters which are either aa, ab, ba or bb.
For each test case, output on a seperate line the gift that Farzi Coder has to build. Note that the empty string is a palindrome.
- 1 ≤ T ≤ 500
- 1 ≤ N ≤ 2000
- Each pair can be either aa, ab, ba or bb
2 4 aa aa bb bb 3 ab ba ab
Case 1: The following palindromes are possible: "aa", "aaaa", "bb", "bbbb", "aabbaa", "bbaabb", "aabbbbaa", "bbaaaabb". Of these, "aabbbbaa" and "bbaaaabb" are of the maximum length. Among these two, "aabbbbaa" is the lexicographically smallest.
Case 2: The palindromes possible here are: "baab" and "abba".
|Tags||acm15amr, ad-hoc, balajiganapath, greedy|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.