C++で文字列を再構成する:同じ文字が隣り合わない並べ替えアルゴリズム

文字列 S が与えられたとき、その文字を並べ替えることで、隣り合う2文字が同じにならないようにできるかどうかを判定します。並べ替えが可能であれば、そのような結果の中から任意の1つを出力し、不可能な場合は空文字列を返します。例えば、入力が「AAB」であれば、出力は「ABA」となります。

解法のアプローチ

この問題は、優先度付きキュー(ヒープ)を使った貪欲法で効率的に解くことができます。ポイントは、残りの出現回数が多い文字から順番に交互に配置していくことです。手順は以下の通りです。

• (整数・文字)のペアを保持する優先度付きキュー pq を作成し、マップ m を定義します
• n := 文字列の長さ
• 各文字の出現頻度をマップ m に記録します
• m 内の各キー・バリューペア p に対して、(p の整数部=出現回数、p の文字部)を pq に挿入します
• ans := 空文字列
• pq が空になるまで、次の処理を繰り返します
  • pq の先頭ペアを one として取り出し、pq から削除します
  • この時点で pq が空である場合:
    • one の整数部(残りカウント)が 1 より大きければ、空文字列を返します
    • そうでなければ、ans に one の文字を追加して ans を返します
  • 続けて、pq の先頭ペアを two として取り出し、pq から削除します
  • ans に one の文字を追加し、さらに two の文字を追加します
  • one と two の整数部をそれぞれ 1 減らします
  • one の整数部が 0 でなければ、one を pq に戻します
  • two の整数部が 0 でなければ、two を pq に戻します
• 最後に ans を返します

なぜこの手法が有効なのか

最も出現回数の多い文字が文字列長の半分を超える(厳密には (n+1)/2 を超える)場合、どのように並べ替えても隣接する同一文字を避けられないため、答えは存在せず空文字列を返します。それ以外の場合は、残数の多い2種類の文字を必ずペアで消費していくため、常に直前の文字と異なる文字を配置でき続け、必ず条件を満たす文字列が構築できます。

計算量

文字列長を n、異なる文字の種類数を k とすると、ループは約 n/2 回実行され、各回でヒープ操作が O(log k) 行われるため、時間計算量は O(n log k)、空間計算量は O(n + k)(答えの格納分とキュー・マップの分)となります。

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例(C++)

#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