Rearrange characters to form a palindrome (if possible) in C++

We are given a string 'str' of any given length. The task is to rearrange the characters so that the output becomes a palindrome string without adding or removing characters from the given input string. A palindrome string is when the characters are arranged in such a way that they sound the same from start to end.

Let's look at various input and output scenarios for this -

Input - String str = "itnin"

Output - If possible, the rearrangement of characters to form a palindrome string is: nitin

Explanation - We are given a variable of type string, assumed to be str. Now we will rearrange the characters of the input string to make it a palindrome string, if not

It will return 'NOT POSSIBLE' if possible. Therefore, the output given the input string is 'nitin'.

Input - String str = "baaaba"

Output - The result of possible character rearrangement to form a palindrome is: aabbaa

Explanation - We are given a variable of string type, assuming it is str. Now we will rearrange the characters of the input string to make it a palindrome string and return 'NOT POSSIBLE' if this is not possible. Therefore, the output given the input string is 'aabbaa'.

The method used in the following program is as follows

• Input a string type variable, assuming it is str, and calculate the size of the string and store it in a name is the variable of length.

• Pass the data to the function Rearrangement(str, length).

• Inside the function Rearrangement(arr, length)

  • Create an unordered_map type variable named 'um', which stores char and integer Type of key-value pairs.

  • Declare an integer type variable total and set it to 0.

  • Create a character type variable 'ch' and string type variables str_1 and str_2.

  • Starts a loop from i to 0 until i is less than length. Inside the loop, set um[str[i]] by incrementing the value 1.

  • Start looping FOR to iterate map 'um'. Inside the loop, check IF it.second % 2 is not equal to 0, then increase total by 1 and set ch to it.first.

  • Check if total is greater than 1 or total = 1 and length % 2 = 0, then 0 will be returned.

  • Start looping FOR to iterate map 'um'. Inside the loop, set str(it.second / 2, it.first) to str, str_1 to str_1 str, and str_2 to str str_2.

  • Check IF total = 1, then return str_1 ch str_2. Otherwise, str_1 str_2 is returned.

• Print the result.

Example

#include <bits/stdc++.h>
using namespace std;
string Rearrangement(string str, int length){
   unordered_map<char, int> um;
   int total = 0;
   char ch;
   string str_1 = "";
   string str_2 = "";

   for (int i = 0; i < length; i++){
      um[str[i]]++;
   }
   for(auto it : um){
      if(it.second % 2 != 0){
         total++;
         ch = it.first;
      }
   }
   if(total > 1 || total == 1 && length % 2 == 0){
      return 0;
   }
   for(auto it : um){
      string str(it.second / 2, it.first);
      str_1 = str_1 + str;
      str_2 = str + str_2;
   }
   if(total == 1){
      return str_1 + ch + str_2;
   }
   else{
      return str_1 + str_2;
   }
}
int main(){
   string str = "itnin";
   int length = str.size();
   cout<<"Rearrangement of characters to form palindrome if possible is: "<<Rearrangement(str, length);
   return 0;
}

Output

If we run the above code, the following output will be generated

Rearrangement of characters to form palindrome if possible is: nitin

The above is the detailed content of Rearrange characters to form a palindrome (if possible) in C++. For more information, please follow other related articles on the PHP Chinese website!