Home » Interview Questions » String Interview Questions » Longest palindrome can be formed by removing or rearranging characters

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

 

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions