C++でスワップを繰り返して作る辞書順最小の文字列

文字列 s と、文字列中のインデックスのペアを格納した配列 pairs が与えられるとします。pairs[i] = [a, b] は、文字列における2つのインデックス（0始まり）を表します。これらのペアに含まれるインデックス同士の文字は、何回でも自由に入れ替えることができます。このとき、スワップを繰り返すことで得られる文字列のうち、辞書順で最小のものを求めてください。

たとえば、入力が s = "dcab"、pairs = [[0,3], [1,2]] の場合、出力は "bacd" になります。まず s[0] と s[3] を入れ替えると s = "bcad" となり、続けて s[1] と s[2] を入れ替えることで s = "bacd" が得られます。

解決のアプローチ

この問題はUnion-Find（素集合データ構造）を使うと効率的に解けます。スワップ可能なインデックス同士を同じグループに統合すると、各グループ内では文字を自由に並べ替えられることが保証されます。したがって、グループごとに文字をソートし、小さい文字から左側（先頭）の位置へ詰めていけば、辞書順最小の文字列が構築できます。

具体的には、次の手順で進めます。

• n := 文字列の長さ。parent := サイズ n の配列を作成し、すべて -1 で初期化する

• サイズ n の文字列 ret を作成し、'*' で埋める

• i を 0 から pairs のサイズまで繰り返す

  • u := pairs[i][0]、v := pairs[i][1]

  • u と v の親（根）が同一なら、次の反復へスキップする

  • parent[getParent(u)] := getParent(v) として、2つのグループを統合する

• サイズ n の配列 arr1 を定義する

• i を 0 から n-1 まで：s[i] を arr1[getParent(i)] に追加する

• i を 0 から n-1 まで：arr1[i] を降順にソートする

• i を 0 から n-1 まで：

  • ret[i] := arr1[getParent(i)] の末尾の要素を代入する

  • arr1[getParent(i)] から末尾の要素を削除する

各グループを降順にソートしておくことで、末尾から取り出す際に必ず「そのグループ内で未使用の最小の文字」を取得できます。その結果、先頭の位置から順に最小の文字を割り当てることが可能になります。

C++の実装例

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

class Solution {
public:
   vector <int> parent;
   int getParent(int x){
      if(parent[x] == -1) return x;
      return parent[x] = getParent(parent[x]);
   }
   string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
      int n = s.size();
      parent = vector <int>(n, -1);
      string ret(n, '*');
      for(int i = 0; i < pairs.size(); i++){
         int u = pairs[i][0];
         int v = pairs[i][1];
         if(getParent(u) == getParent(v)) continue;
         parent[getParent(u)] = getParent(v);
      }
      vector < char > arr1[n];
      for(int i = 0; i < n; i++){
         arr1[getParent(i)].push_back(s[i]);
      }
      for(int i = 0; i < n; i++){
         sort(arr1[i].rbegin(), arr1[i].rend());
      }
      for(int i = 0; i < n; i++){
         ret[i] = arr1[getParent(i)].back();
         arr1[getParent(i)].pop_back();
      }
      return ret;
   }
};

計算量の目安

Union-Findによるグループ化は経路圧縮によりほぼ線形時間で動作し、全体の計算量は各グループのソートを含めて O(n log n) 程度に収まります。そのため、文字列長やペア数が大きいケースでも実用的な速度で処理できます。

入力

"dcab"
[[0,3],[1,2]]

出力

"bacd"