在C ++中重组字符串

假设我们有一个字符串S，请检查是否可以重新排列字母，以使彼此相邻的两个字符不同。如果可能，输出任何可能的结果。如果不可能，则返回空字符串。因此，如果输入像“ AAB”，那么输出将是“ ABA”。

为了解决这个问题，我们将遵循以下步骤-

• 创建一个称为pq的整数字符对的优先级队列，定义一个映射m

• n：=字符串的大小

• 将字符频率存储在映射m中

• 对于m中的每个键值对p

• 插入（p的整数部分，p的字符部分）

• ans：=空字符串

• 当pq不为空时

• 如果整数部分> 1，则返回空字符串

• ans：= ans +一个字符的一部分

• 返回ans

• 设置一个：= pq中的顶级对，并删除pq中的顶级对

• 如果pq为空，则

• 两个：=来自pq的顶部对，并删除来自pq的顶部对

• ans：= ans +一个字符的一部分

• ans：= ans +两个字符的一部分

• 将一和二的整数部分加1

• 如果1的整数部分不为0，则将1插入pq

• 如果2的整数部分不为0，则将1插入pq

• 返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string reorganizeString(string S) {
      priority_queue <pair <int, char>> pq;
      map <char, int> m;
      int n = S.size();
      for(int i = 0; i < n; i++){
         m[S[i]]++;
      }
      map <char, int> :: iterator i = m.begin();
      while(i != m.end()){
         pq.push({i->second, i->first});
         i++;
      }
      string ans = "";
      while(!pq.empty()){
         pair <int, char> one = pq.top();
         pq.pop();
         if(pq.empty()){
            if(one.first > 1)
            return "";
            ans += one.second;
            return ans;
         }
         pair <int, char> two = pq.top();
         pq.pop();
         ans += one.second;
         ans += two.second;
         //cout << ans << endl;
         one.first--;
         two.first--;
         if(one.first)pq.push(one);
         if(two.first)pq.push(two);
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   cout << ob1.reorganizeString("AAB") << endl;
   return 0;
}

输入项

S = "AAB"
ob1.reorganizeString("AAB")

输出结果

ABA