Rearrange string to maximize number of palindromic substrings in C++

We get a string "str" ​​of any given length. The task is to rearrange the characters in such a way that, without adding or removing characters from the given input string, there will be the largest substring that becomes a palindrome string. A palindrome string is a string of characters arranged in such a way that they sound the same from beginning to end.

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

Input− string str = "itnin"

Output − Rearrange the string to maximize the number of palindromic substrings: iinnt.

Explanation- We get a string type variable, say str. Now we will rearrange the characters of the input string to make it a maximum palindrome string and return "NOT POSSIBLE" if this is not possible. Therefore, the output given the input string is "iinnt".

Input− string str = "abaaaabb"

Output − Rearranging the string to maximize the number of palindrome substrings is: aaaaabbb.

Explanation − We give a string type variable, such as str. Now we will rearrange the characters of the input string to make it a maximum palindrome string and return "NOT POSSIBLE" if this is not possible. So the output of the given input string is aaaaabbb'

The method used in the following program is as follows

• Enter a string variable Suppose you enter str and calculate the size of the string and stores it in a variable named length.

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

• Inside the function Rearr_string(str, length)

  • Declare an integer type array with a size of 26, such as arr[26] and use 0 Initialize it.

  • Declare a temporary variable "temp" of string type.

  • Start looping FOR from i to 0 until i is less than length. Inside the loop, set arr[str[i] - 'a'] .

  • Start looping FOR from i to 0 until i is less than 26. Inside the loop, start another FOR loop from j to 0 until j is less than arr[i]. Inside the loop, set temp to temp (char)(97 i).

  • Return temp.

• Print the result.

Example

#include <bits/stdc++.h>
using namespace std;
string Rearr_string(string str, int length){
   int arr[26] = { 0 };
   string temp = "";
   for(int i = 0; i < length; i++){
      arr[str[i] - &#39;a&#39;]++;
   }
   for(int i = 0; i < 26; i++){
      for(int j = 0; j < arr[i]; j++){
         temp = temp + (char)(97 + i);
      }
   }
   return temp;
}
int main(){
   string str = "itinn";
   int length = str.length();
   cout<<"Rearrangement of the string to maximize the number of palindromic substrings is: "<<Rearr_string(str, length);
   return 0;
}

Output

If we run the above code it will generate the following output

Rearrangement of the string to maximize the number of palindromic substrings is: iinnt

The above is the detailed content of Rearrange string to maximize number of palindromic substrings in C++. For more information, please follow other related articles on the PHP Chinese website!