PythonでK類似文字列の最小スワップ回数Kを求める方法【BFSで解く】

問題の概要

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

ここでは、互いにアナグラムの関係にある2つの文字列 s と t が与えられ、s と t がK類似となる最小のKを求めることを目標とします。

たとえば、入力が s = "abc"、t = "bac" の場合、出力は 1 になります。「a」と「b」を1回入れ替えるだけで "abc" → "bac" と変換できるためです。

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

この問題は、各文字列の状態をノード、1回のスワップで移行できる関係をエッジとみなしたグラフとして捉えると、幅優先探索（BFS）で最短のスワップ回数を求められます。開始状態 s から出発し、目標状態 t に到達するまでの最少ステップ数がそのまま答えになります。

neighbors() 関数の役割

引数で受け取った文字列について、1回のスワップで作れる次の状態候補をすべて列挙するジェネレータ関数です。処理の流れは次のとおりです。

• 各インデックス i とその文字 c を先頭から走査し、c が t[i] と異なる最初の位置でループを抜けます。それより手前の位置はすでに正しい文字が揃っているため、そこを崩すスワップは無駄になるからです。
• 続いて j を i + 1 から末尾まで動かし、new_data[j] が t[i] と一致する場合に new_data[i] と new_data[j] を入れ替えます。入れ替えた文字列を yield で返した後、元に戻して次の候補を探します。

BFS本体の処理手順

1. キュー q を作成し、ペア (s, 0) を挿入します（第2要素は現在のスワップ回数）。
2. 既訪問管理用の集合 seen を作成し、s を登録しておきます。
3. q が空でない限り、以下を繰り返します。
   • キューの先頭から (u, swap_cnt) を取り出します。
   • u が t と一致していれば、swap_cnt を返します。
   • neighbors() が返す各候補 v について、未訪問なら seen に追加し、(v, swap_cnt + 1) をキューの末尾へ追加します。

探索が完了しても t に到達できない場合は 0 を返します。

Pythonでの実装例

from collections import deque

def solve(s, t):
    def swap(data, i, j):
        data[i], data[j] = data[j], data[i]

    def neighbors(new_data):
        for i, c in enumerate(new_data):
            if c != t[i]:
                break

        for j in range(i + 1, len(new_data)):
            if new_data[j] == t[i]:
                swap(new_data, i, j)
                yield "".join(new_data)
                swap(new_data, i, j)

    q = deque([(s, 0)])
    seen = set([s])
    while q:
        u, swap_cnt = q.popleft()
        if u == t:
            return swap_cnt
        for v in neighbors(list(u)):
            if v not in seen:
                seen.add(v)
                q.append((v, swap_cnt + 1))
    return 0

s = "abc"
t = "bac"
print(solve(s, t))

入力

s = "abc", t = "bac"

出力

1

計算量と実装のポイント

最悪の場合、状態数は文字列長 n に対して最大 n! 通りとなり、計算量は O(n! × n²) 程度に増大します。ただし、BFSは必ず最短のスワップ回数を見つけることが保証されており、既訪問集合 seen によって同じ状態を二度と探索しないため、重複状態が多い場合でも効率よく動作します。

さらに、neighbors() で「まだ一致していない最初の位置」だけをスワップ対象にすることで、無駄な候補を大幅に削減できる点も、この実装における重要な工夫です。