C++で文字列を再編成します

文字列Sがあるとします。隣接する2つの文字が同じにならないように、文字を再配置できるかどうかを確認します。それが可能な場合は、可能な結果を​​出力します。それが不可能な場合は、空の文字列を返します。したがって、入力が「AAB」のような場合、出力は「ABA」になります。

これを解決するには、次の手順に従います-

• pqと呼ばれる整数文字ペアの優先キューを作成し、1つのマップmを定義します
• n：=文字列のサイズ
• 文字の頻度をマップmに保存します
• m
  の各キーと値のペアp
  • 挿入（pの整数部分、pの文字部分）
• ans：=空の文字列
• pqが空でない間
  • pqから1つ：=トップペアを設定し、pqからトップペアを削除します
  • pqが空の場合、
    • 1の整数部分>1の場合、空の文字列を返します
    • ans：=ans+1つの文字部分
    • 回答を返す
  • two：=pqからトップペア、pqからトップペアを削除
  • ans：=ans+1つの文字部分
  • ans：=ans+2つの文字部分
  • 1と2の整数部分を1つ増やします
  • 1の整数部分が0でない場合は、1をpqに挿入します
  • 2の整数部分が0でない場合は、1をpqに挿入します
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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