Longest Palindrome can be Formed by Removing or Rearranging Characters

Problem Statement

In the “Longest Palindrome can be Formed by Removing or Rearranging Characters” problem we have given a string “s”. Find the longest palindrome that can be constructed by removing or rearranging some characters or possibly zero characters from the string. There may be multiple solutions possible, you can print any one of them.

Input Format

The first and only one line containing a string “s”.

Output Format

Print a string that represents the Longest Palindrome which is Formed by Removing or Rearranging Characters of string “s”.

Constraints

• 1<=|s|<=10^6
• s[i] must be a lower case English alphabet

Example

abc

a

Explanation: Here the count of a is 1, the count of b is 1, and the count of c is also 1. So, here 3 answers are possible which are “a”, “b”, or “c”.

aabb

abba

Explanation: Here the count of a is 2 and the count of b is 2. So our start contains “ab”, mid is null, and end is “ba”. So, our final answer will be “abba”.

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. Declare a freq[] array initially all values are initialized with 0 and an integer flag=0.

2. Store the frequency or count of characters in the freq[] array.

3. Simply run one loop to visit every character ‘a’ to ‘z’.

4. If the count of a character is odd and flag value is zero. We make this char as mid. And add that character freq[ch]/2 times in the start.

5. Else add current char freq[ch]/2 times at the end of the start.

6. The reverse of the start will be our end.

7. So, our final answer will be the concatenation of start, mid, end.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int freq[26]={0};
   for(int i=0;i<n;i++)
   {
       freq[s[i]-'a']++;
   }
   string start="",mid="", end=""; 
   int flag=0;
   for(int i=0;i<26;i++)
   {
       if(freq[i]%2==1 && flag==0)
       {
           flag=1;
           mid+= ('a'+i);
           for(int j=0;j<freq[i]/2;j++)
           {
               start+=('a'+i);
           }
       }
       else
       {
           for(int j=0;j<freq[i]/2;j++)
           {
               start+=('a'+i);
           }
       }
   }
   end = start;
   reverse(end.begin(), end.end());
   string ans="";
   ans+=start;
   ans+=mid;
   ans+=end;
   cout<<ans<<endl;
   return 0;
}

import java.util.Scanner;

class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        int n=s.length();
        int freq[] = new int[26]; 
        for(int i=0;i<26;i++) 
        {
            freq[i]=0; 
        }
        for(int i=0;i<n;i++) 
        {
            freq[s.charAt(i)-'a']++; 
        }
        String start="",mid="", end=""; 
        int flag=0;
        for(int i=0;i<26;i++)
        {
            if(freq[i]%2==1 && flag==0)
            {
                flag=1;
                char ch = (char)('a'+i);
                mid+=ch;
                for(int j=0;j<freq[i]/2;j++)
                {
                    start+=ch;   
                }
            }
            else
            {
                for(int j=0;j<freq[i]/2;j++)
                {
                    char ch = (char) ('a'+i);
                    start+=ch;
                }
            }
        }
        end = start;
        StringBuilder temp = new StringBuilder(end);  
        temp.reverse();
        String ans="";
        ans+=start;
        ans+=mid;
        ans+=temp;
        System.out.println(ans);
    }
}

duvwedcvhwwecv

cdevwhwvedc

Complexity Analysis

Time Complexity

O(n) where n is the size of the given string “s”. Here we simply store the frequency of every character present in the string “s”. Perform some operation as per the need in linear time and get the answer.

Space Complexity

O(n) because we need to store the final answer. And the maximum length of the final string will be equal to the given string.