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++

#include <iostream>
#include <unordered_map>
using namespace std;

// Construct the longest palindrome by shuffling or deleting
// characters from a given string
string longestPalindrome(string const &str)
{
	// create a frequency map for characters of given string
	unordered_map<char, int> freq;
	for (char ch: str) {
		freq[ch]++;
	}

	char mid_char;	  // stores odd character
	string left;		// stores left substring

	// iterate through the frequency map
	for (auto p: freq)
	{
		char ch = p.first;		// get current character
		int count = p.second;	 // get character frequency

		// if the frequency of current character is odd
		// update mid to current char (and discard old one)
		if (count & 1) {
			mid_char = ch;
		}

		// append half of the characters to the left substring
		// (other half goes to the right substring in reverse order)
		left.append(count/2, ch);
	}

	// right substring will be reverse of left substring
	string right(left.rbegin(), left.rend());

	// return string formed by the left substring, mid character (if any)
	// and the right substring
	return (left + mid_char + right);
}

// main function
int main()
{
	string str = "ABBDAB";

	cout << "The Longest Palindrome is " << longestPalindrome(str);

	return 0;
}

#include <iostream>

#include <unordered_map>

using namespace std;

// Construct the longest palindrome by shuffling or deleting

// characters from a given string

string longestPalindrome(string const &str)

{

// create a frequency map for characters of given string

unordered_map<char, int> freq;

for (char ch: str) {

freq[ch]++;

}

char mid_char; // stores odd character

string left; // stores left substring

// iterate through the frequency map

for (auto p: freq)

{

char ch = p.first; // get current character

int count = p.second; // get character frequency

// if the frequency of current character is odd

// update mid to current char (and discard old one)

if (count & 1) {

mid_char = ch;

}

// append half of the characters to the left substring

// (other half goes to the right substring in reverse order)

left.append(count/2, ch);

}

// right substring will be reverse of left substring

string right(left.rbegin(), left.rend());

// return string formed by the left substring, mid character (if any)

// and the right substring

return (left + mid_char + right);

}

// main function

int main()

{

string str = "ABBDAB";

cout << "The Longest Palindrome is " << longestPalindrome(str);

return 0;

}

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

C++

Sharing is caring:

Leave a Reply