我们给定了一个字符串，假设为str，长度可以是任意值。任务是重新排列给定的字符串，使得在结果字符串中不会有相同的相邻字符排在一起。

让我们看看各种输入输出场景：

输入 − 字符串str = "itinn"

输出 − 重新排列字符串中的字符，使得相邻的两个字符不相同，结果为：initn。

解释 − 我们给定了一个字符串类型的变量，假设为str。现在我们将重新排列输入字符串的字符，使得没有两个相同的字符出现在同一个位置，即将'nn'移动到不相邻的位置。所以最终的结果是 字符串将会是 ‘initn’.

输入 − 字符串 str = "abbaabbaa"

输出 − 字符串中字符重新排列，使得相邻的字符不相同: ababababa

解释 − 我们给定了一个字符串类型的变量，假设为 str。现在我们将重新排列输入字符串的字符，使得没有两个相同的字符出现在同一个位置，即移动 ‘bb’, ‘aa’, ‘bb’, ‘aa’，因为它们是相同的并且相邻。所以最终的字符串将会是 ‘ababababa’。

下面程序中使用的方法如下

• 输入一个字符串类型的变量，假设为 str，并计算字符串的大小并将其存储在一个名为 length 的变量中。

• 检查如果 length 为 0，则返回。

• 将数据传递给函数 Rearrangement(str, length)。

• 在函数 Rearrangement(arr, length) 内部

  • 设置字符串的大小为 (length + 1)/2。

  • 声明一个向量类型的变量 vec(26, 0)，它将存储整数类型的数据，以及一个字符串类型的指针 ptr(length, ‘ ‘)。还声明一个临时变量 temp，类型为整数，值为 0。

  • 开始循环 FOR 来迭代 str。在循环内部，设置 vec[it - ‘a’]++。

  • 创建一个字符类型的变量 ch，并将其设置为调用 maximum(vec) 函数的结果。

  • 声明一个整数类型的变量 total，并将其设置为 vec[ch - ‘a’]。

  • 检查如果 total 大于 size，则返回。

  • 开始循环 WHILE total，然后将 ptr[temp] 设置为 ch，将 temp 设置为 temp + 2，并将 total 减 1。

  • 将 vec[ch - 'a'] 设置为 0。开始循环 FOR，从 i 到 0，直到 i 小于 26。在循环内部，开始 while 循环，当 vec[i] 大于 0 时，将 temp 设置为 (temp >= length) ? 1 : temp，将 ptr[temp] 设置为 'a' + i，将 temp 设置为 temp + 2，并将 vec[i] 减 1。

  • 返回 ptr

• 在函数 char maximum(const vector<int>& vec) 内部

  • 声明一个整数类型的变量 high，并将其设置为 0，以及一个字符类型的变量 c。

  • 开始循环 FOR，从 i 到 0，直到 i 小于 26。在循环内部，检查如果 vec[i] 小于 high，则将 high 设置为 vec[i]，将 c 设置为 'a' + i。

  • 返回 c

• 打印结果。

例子

#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 = 'a' + i;
      }
   }
   return c;
}
string Rearrangement(string str, int length){
   int size = (length + 1) / 2;
   vector<int> vec(26, 0);
   string ptr(length, ' ');
   int temp = 0;
   for(auto it : str){
      vec[it - 'a']++;
   }
   char ch = maximum(vec);
   int total = vec[ch - 'a'];
   if(total > size){
      return "";
   }
   while(total){
      ptr[temp] = ch;
      temp = temp + 2;
      total--;
   }
   vec[ch - 'a'] = 0;
   for(int i = 0; i < 26; i++){
      while (vec[i] > 0){
         temp = (temp >= length) ? 1 : temp;
         ptr[temp] = 'a' + 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;
}

输出

如果我们运行上述代码，将会生成以下输出

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