C++で解く「類似文字列グループ」問題 ― Union-Findを使った効率的な実装

問題の概要

2つの文字列 X と Y が「類似(similar)」しているとは、次のいずれかの条件を満たすことを指します。

• X の2文字を入れ替えることで Y と等しくできる
• X と Y が完全に一致している

例を挙げてみましょう。「tars」と「rats」は t と r を入れ替えることで互いに変換できるため類似しています。また、「rats」と「arts」も r と a を入れ替えることで一致するため類似しています。しかし、「star」は「tars」「rats」「arts」のどれとも1回の入れ替えでは一致しないため、類似していません。

このとき、文字列たちは類似関係によって次の2つの連結グループを形成します。

• {"tars", "rats", "arts"}
• {"star"}

注目すべき点として、「tars」と「arts」は直接には類似していませんが、同じグループに属しています。これは、各グループが「ある単語は、そのグループ内の少なくとも1つの他の単語と類似していれば属せる」という推移的なつながりで定義されているためです。

ここで、文字列のリスト A が与えられます。A 内のすべての文字列は、互いにアナグラム(並べ替えて一致する文字列)であることが保証されています。このとき、グループの総数を求めるのが本問題の目的です。

例えば、入力が ["tars", "rats", "arts", "star"] の場合、出力は 2 となります。

解法のアプローチ

この問題はUnion-Find(素集合データ構造)を使うことで効率的に解けます。全体の方針は以下の通りです。

1. 最初はすべての文字列が独立したグループ(数 = n)だと仮定する。
2. すべての文字列ペアについて「類似しているか」を判定する。
3. 類似しており、かつまだ同じグループに属していない場合は、2つのグループを統合し、グループ数を1減らす。

使用する関数

• parent 配列・rank 配列: Union-Find の内部状態を管理します。
• getParent(x): 要素 x の根(代表元)を再帰的に求めます。経路圧縮により、探索途中のノードの親を根に直接つなぎ替えることで、以降の計算を高速化しています。
• unionn(x, y): 2つの要素をマージします。すでに同じグループなら false を返し、そうでなければ rank(木のサイズ)を比較して小さい方を大きい方に接続し、true を返します。
• ok(s1, s2): 2つの文字列を先頭から比較し、異なる文字の位置の数をカウントします。相違点が2以下であれば true を返します(1回の入れ替えで一致するか、完全一致かの判定に対応)。

メイン処理の流れ

• ret を文字列数 n で初期化します。
• parent をすべて -1、rank をすべて 1 で初期化します。
• すべてのペア (i, j) について、ok(A[i], A[j]) が true かつ unionn(i, j) が成功した場合、ret を1減らします。
• 最終的な ret がグループ数となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> parent;
   vector<int> rank;
   int getParent(int x){
      if (parent[x] == -1)
      return x;
      return parent[x] = getParent(parent[x]);
   }
   bool unionn(int x, int y){
      int parX = getParent(x);
      int parY = getParent(y);
      if (parX == parY)
      return false;
      if (rank[parX] >= rank[parY]) {
         rank[parX] += rank[parY];
         parent[parY] = parX;
      } else {
         rank[parY] += rank[parX];
         parent[parX] = parY;
      }
      return true;
   }
   bool ok(string& s1, string& s2){
      int cnt = 0;
      for (int i = 0; i < s1.size(); i++) {
         if (s1[i] != s2[i])
         cnt++;
         if (cnt > 2)
         return false;
      }
      return true;
   }
   int numSimilarGroups(vector<string>& A){
      int ret = 0;
      int n = A.size();
      ret = n;
      parent = vector<int>(n, -1);
      rank = vector<int>(n, 1);
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            if (ok(A[i], A[j])) {
               if (unionn(i, j))
               ret--;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"tars","rats","arts","star"};
   cout << (ob.numSimilarGroups(v));
}

入力例

{"tars","rats","arts","star"}

出力例

2

計算量とポイント

この実装では、すべての文字列ペアを比較するため O(n² × L)(L は文字列長)の判定コストがかかりますが、Union-Find に経路圧縮とランク(サイズ)によるマージを組み合わせることで、グループ統合の操作はほぼ定数時間で処理できます。その結果、全体として非常に効率的にグループ数を求めることができます。

特に重要なのは、「直接類似していない文字列同士でも、類似関係を介して間接的につながっていれば同一グループとみなす」という点です。この推移的な関係の管理こそ、Union-Find が最も得意とする処理であり、グラフの連結成分を数える問題として捉えると理解しやすくなります。