Construct the Longest Palindrome by Shuffling or Deleting Characters from a String

Write a efficient algorithm to construct the longest palindrome by shuffling or deleting characters from a given string.


For example,

Output: The longest palindrome is BABAB (or BADAB or ABBBA or ABDBA)

Input: ABCDD
Output: The longest palindrome is DAD (or DBD or DCD)


We know that the left and right half of a palindrome contains same set of characters in reverse order, and optionally a middle character which can be anything. The idea is to find all even occurring characters and construct left half of the palindrome from them using half their count. Their ordering don’t matter as shuffling is permitted. Then we can easily construct the right half from the left half by reversing it. All odd occurring characters are ignored except one, which forms the middle character of the resultant palindromic string.


Download   Run Code


The Longest Palindrome is BABAB

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n) where n is length of the string.

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of