C++で文字列のK類似性を求めるプログラム｜最小スワップ回数をBFSで探索

問題の概要

2つの文字列 s と t があるとします。s 内の2つの文字の位置をちょうどK回入れ替えることで t と同一の文字列にできるとき、これらの文字列は「K類似（K-similar）」であると定義されます。

ここで、互いにアナグラム（同じ文字で構成された並べ替え）の関係にある2つの文字列 s と t が与えられるので、s と t が K類似となる最小の K を求めましょう。

例えば、入力が s = "abc"、t = "bac" の場合、出力は 1 となります。

解決アプローチ：幅優先探索（BFS）

この問題は、文字列の各状態をグラフのノードとみなし、「1回のスワップ」をエッジとして幅優先探索（BFS）を行うことで効率的に解けます。BFSは最短距離から順に探索するため、最小のスワップ回数 K を必ず見つけられます。

探索の手順

• swapp() 関数の定義： 文字列 s とインデックス i、j を受け取り、s[i] と s[j] を入れ替えます。
• メイン処理：
  • A が B と等しい場合は 0 を返します。
  • 訪問済みの文字列を管理するセット visited を用意し、A を追加します。
  • キュー q を作成し、A を追加します。
  • レベル lvl を 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] の場合（すでに正しい位置にある文字を崩してしまう）
  • 条件を満たすペア (i, j) を swapp() で入れ替えます。
  • curr が B と一致したら、現在の lvl を返します。
  • visited に存在しない場合は、visited に追加してキューへ push します。
  • その後、再度 swapp() を呼び出して元の状態に戻します（バックトラック）。
• s と t はアナグラムなので必ず解が存在しますが、万が一見つからない場合は -1 を返します。

この枝刈りにより、「正しい位置にある文字を壊さず」「i番目の不一致を直接修正できる」スワップだけを探索対象にできるため、無駄な状態展開が大幅に削減されます。

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

まとめ

本手法では、BFSによるレベルごとの探索で最小スワップ回数を保証しつつ、3つの枝刈り条件によって探索空間を絞り込んでいます。計算量は最悪ケースでは文字列長に対して指数的になりますが、重複状態の除外（visitedセット）と不一致位置のみを対象とする戦略により、実用的な入力に対しては高速に動作します。