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;
}
Try It

 


Next > < Prev
Scroll to Top