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.


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)


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++)
    //start, mid and end.
    string start = "", mid = "", end = "";
    for (char ch = 'a'; ch <= 'z'; ch++)
        if (count[ch] & 1)
            mid = ch;
            for (int i = 0; i < count[ch]/2 ; i++)
    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


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions