# Longest palindrome can be formed by removing or rearranging characters

## Find the longest palindrome that can be constructed by removing or rearranging characters from the string.

### Example

a) Input string: abc
Output: a or b or c

b) Input string: aabb
Output: baab or abba

c) Input string: abca
Output: aba or aca

Time complexity : O(n)

## Algorithm

Let there be three parts of palindrome → start, middle, end Mid should be of one character or Null, end is reverse of start. And size string is 2n + 1 or 2n.

1. We store frequencies of the characters in count array.

2. If count of a character is odd, we make it as mid. Update it with next odd if found.

3. If count is even(n), we push n/2 of n characters to start.

4. We reverse of start will be end.

5. We add start + mid + end → output string.

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

string FindLongestPalindrome(string input_string)
{
//Count array to store count of charcters
int count[256] = {0};
for (int i = 0; i < input_string.size(); i++)
{
count[input_string[i]]++;
}
//start, mid and end.
string start = "", mid = "", end = "";
for (char ch = 'a'; ch <= 'z'; ch++)
{
if (count[ch] & 1)
{
mid = ch;
count[ch--]--;
}
else
{
for (int i = 0; i < count[ch]/2 ; i++)
{
start.push_back(ch);
}
}
}
end = start;
//end is reverse of start
reverse(end.begin(), end.end());
return start + mid + end;
}

//Main function
int main()
{
string input_string = "abcc";
cout<<"Output palindrome string is: "<<FindLongestPalindrome(input_string);
return 0;
}``````

Scroll to Top