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,


Input: ABBDAB
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.

C++

Download   Run Code

Output:

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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of