C++で解く「K類似文字列」問題：最小スワップ回数をBFSで求める方法

問題の概要

2つの文字列 A と B が与えられます。A に含まれる2つの文字の位置をちょうど K 回入れ替えることで B と同じ文字列にできるとき、A と B は「K類似（K-similar）」であると定義されます。ここでは、互いにアナグラムの関係にある2つの文字列 A と B に対して、両者が K 類似となる最小の K を求めます。

たとえば、入力が A = "abc"、B = "bac" の場合、先頭の2文字を1回入れ替えるだけで B に変換できるため、答えは 1 になります。

解法の考え方：幅優先探索（BFS）

この問題は幅優先探索（BFS）で解くのが効果的です。探索の各レベルを「スワップを実行した回数」とみなし、初めて文字列 B に到達した時点のレベルが、そのまま最小のスワップ回数（= 求める K）になります。

アルゴリズムの手順

1. 関数 swapp() の定義：文字列 s とインデックス i、j を受け取り、x := s[i]、y := s[j] として s[i] := y、s[j] := x とすることで2文字を入れ替えます。
2. 初期チェック：A が B と同一の場合は 0 を返します。
3. BFSの準備：訪問済みの文字列を管理する集合 visited を作成して A を登録し、キュー q を作成して A を挿入します。
4. レベルごとの探索：lvl = 1 から開始し、キューが空になるまで1周ごとに lvl を +1 しながら以下を繰り返します。
   • sz := キューの現在のサイズとし、sz 回だけ次の処理を行います。
   • curr := キューの先頭要素を取り出し、要素を削除します。
   • i := 0 とし、curr[i] == B[i] が成り立つ間 i を増加させ、最初に不一致となる位置を見つけます。
   • j を i + 1 から文字列の末尾まで動かしながら、次のいずれかに該当する場合はスキップします。
     • curr[i] == curr[j] の場合（入れ替えても変化がない）
     • curr[j] != B[i] の場合（位置 i を修復できない）
     • curr[j] == B[j] の場合（すでに正しい位置にある文字を壊さないため）
   • swapp(curr, i, j) で実際に文字を入れ替えます。
   • curr == B となったら、その時点の lvl を返します。
   • curr が未訪問であれば、visited に追加し、q にも挿入します。
   • 最後に swapp(curr, i, j) を再度呼び出し、文字列を元の状態に戻します（バックトラック）。
5. 終了条件：キューが空になっても B に到達できなければ -1 を返します（A と B がアナグラムであれば必ず到達可能です）。

アルゴリズムのポイント

この実装には、探索空間を大きく絞り込むための工夫が含まれています。

• 最初の不一致位置からだけ試す：それ以前の文字はすでに B と一致しているため、そこを崩す操作は最短解になり得ません。
• 正しい位置にある文字を保護：curr[j] == B[j] となる j を入れ替え対象から除外することで、無駄な状態遷移を防ぎます。
• visited による重複排除：同じ文字列を二度と探索しないため、状態数の爆発的な増加を抑制できます。

C++での実装例

以下は、上記のアルゴリズムをそのまま C++ で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int kSimilarity(string A, string B) {
        if (A == B)
            return 0;
        unordered_set<string> visited;
        visited.insert(A);
        queue<string> q;
        q.push(A);
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                string curr = q.front();
                q.pop();
                int i = 0;
                while (i < curr.size() && curr[i] == B[i])
                    i++;
                for (int j = i + 1; j < curr.size(); j++) {
                    if (curr[i] == curr[j])
                        continue;
                    if (curr[j] != B[i])
                        continue;
                    if (curr[j] == B[j])
                        continue;
                    swapp(curr, i, j);
                    if (curr == B)
                        return lvl;
                    if (!visited.count(curr)) {
                        visited.insert(curr);
                        q.push(curr);
                    }
                    swapp(curr, i, j);
                }
            }
        }
        return -1;
    }
    void swapp(string &s, int i, int j) {
        char x = s[i];
        char y = s[j];
        s[i] = y;
        s[j] = x;
    }
};
main() {
    Solution ob;
    cout << (ob.kSimilarity("abc", "bac"));
}

入力

"abc", "bac"

出力

1

まとめ

文字列長を n、探索対象となる状態の総数を S とすると、1つの状態あたり最大 O(n²) 通りの入れ替え候補を調べるため、全体の計算量は O(S·n²) となります。ただし、「不一致位置からのみ試す」「正しい位置を壊さない」という剪定条件により S は大きく抑えられるため、実用的な入力サイズであれば高速に動作します。また、BFS の性質上、最初に B に到達した経路が必ず最小スワップ回数になる点も、この解法の大きな強みです。