Longest palindrome can be formed by removing or rearranging characters

0
276
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

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here