Rearrange the characters in a string so that any two adjacent characters are different, implemented in C++

We are given a string, assuming it is str, the length can be any value. The task is to rearrange the given string so that identical adjacent characters do not line up together in the resulting string.

Let us look at various input and output scenarios:

Input − String str = "itinn"

Output − Rearrange the characters in the string so that two adjacent characters are different. The result is: initn.

Explanation − We are given a variable of string type, assuming it is str. Now we will rearrange the characters of the input string so that no two identical characters appear in the same position, i.e. move 'nn' to a non-adjacent position. So the final result is The string will be 'initn'.

Input − String str = "abbaabbaa"

Output − Rearrange the characters in the string , making adjacent characters different: ababababa

Explanation − We are given a variable of string type, assuming it is str. Now we will rearrange the characters of the input string so that no two same characters appear in the same position i.e. move 'bb', 'aa', 'bb', 'aa' since they are the same and adjacent . So the final string will be ‘ababababa’.

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 length variable.

• Check if length is 0, then return.

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

• Inside function Rearrangement(arr, length)

  • Set the size of the string to (length 1)/2.

  • Declare a vector type variable vec(26, 0), which will store integer type data, and a string type pointer ptr(length, ‘ ‘). Also declare a temporary variable temp, of type integer and value 0.

  • Start looping FOR to iterate str. Inside the loop, set vec[it - ‘a’] .

  • Create a character type variable ch and set it to the result of calling the maximum(vec) function.

  • Declare an integer type variable total and set it to vec[ch - ‘a’].

  • Check if total is greater than size, then return.

  • Start looping WHILE total, then set ptr[temp] to ch, temp to temp 2, and decrement total by 1.

  • Set vec[ch - 'a'] to 0. Start looping FOR from i to 0 until i is less than 26. Inside the loop, start the while loop, when vec[i] is greater than 0, set temp to (temp >= length) ? 1: temp, set ptr[temp] to 'a' i, set temp to temp 2, and decrement vec[i] by 1.

  • Return ptr

• Inside the function char maximum(const vector& vec)

  • Declare an integer type variable high and set it to 0, and a character type variable c.

  • Start looping FOR from i to 0 until i is less than 26. Inside the loop, check if vec[i] is less than high, then set high to vec[i] and c to 'a' i.

  • Return c

• Print result.

Example

#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
   int high = 0;
   char c;
   for(int i = 0; i < 26; i++){
      if(vec[i] > high){
         high = vec[i];
         c = &#39;a&#39; + i;
      }
   }
   return c;
}
string Rearrangement(string str, int length){
   int size = (length + 1) / 2;
   vector<int> vec(26, 0);
   string ptr(length, &#39; &#39;);
   int temp = 0;
   for(auto it : str){
      vec[it - &#39;a&#39;]++;
   }
   char ch = maximum(vec);
   int total = vec[ch - &#39;a&#39;];
   if(total > size){
      return "";
   }
   while(total){
      ptr[temp] = ch;
      temp = temp + 2;
      total--;
   }
   vec[ch - &#39;a&#39;] = 0;
   for(int i = 0; i < 26; i++){
      while (vec[i] > 0){
         temp = (temp >= length) ? 1 : temp;
         ptr[temp] = &#39;a&#39; + i;
         temp = temp + 2;
         vec[i]--;
      }
   }
   return ptr;
}
int main(){
   string str = "itinn";
   int length = str.length();
   if(length == 0){
      cout<<"Please enter a valid string";
   }
   string count = Rearrangement(str, length);
   if(count == ""){
      cout<<"Please enter a valid string";
   }
   else{
      cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
   }
   return 0;
}

Output

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

Rearrangement of characters in a string such that no two adjacent are same is: initn

The above is the detailed content of Rearrange the characters in a string so that any two adjacent characters are different, implemented in C++. For more information, please follow other related articles on the PHP Chinese website!