Pythonでアナグラム同士の文字列を一致させるための最小スワップ回数を求めるプログラム

問題の概要

互いにアナグラムの関係にある2つの文字列 S と T が与えられたとします。このとき、S 側で文字の入れ替え(スワップ)を行い、S を T とまったく同じ文字列にするために必要な最小のスワップ回数を求めるのがこの問題です。

たとえば、S = "kolkata"、T = "katloka" の場合、答えは 3 になります。次のような順序で入れ替えることで一致させられるからです。

[katloka(初期状態) → kotlaka → koltaka → kolkata]

解法のアプローチ

この問題は、再帰とバックトラッキングを組み合わせることで解けます。各位置について「どの文字と入れ替えればよいか」を全通り試し、その中で最小の手数を選ぶイメージです。具体的な手順は以下の通りです。

1. 関数 util() を定義します。引数は S、T、現在の位置 i です。
2. i が S の長さ以上になったら、すべての位置が一致しているので 0 を返します。
3. S[i] と T[i] がすでに同じなら、入れ替えは不要なので util(S, T, i + 1) を返します。
4. そうでなければ、x = T[i] として、必要な文字を特定します。
5. ret を十分に大きい値(ここでは 99999)で初期化します。
6. j を i + 1 から T の末尾までループさせます。
   • x が S[j] と等しい場合:
     • S[i] と S[j] を入れ替えます。
     • ret = min(ret, 1 + util(S, T, i + 1)) で最小値を更新します。
     • S[i] と S[j] を元に戻して(バックトラック)、別の候補も試せるようにします。
7. 最後に ret を返します。

メイン側の処理では、単に util(S, T, 0) を呼び出して結果を返すだけです。

実装例(Python)

class Solution:
    def util(self, S, T, i):
        S = list(S)
        T = list(T)
        if i >= len(S):
            return 0
        if S[i] == T[i]:
            return self.util(S, T, i + 1)
        x = T[i]
        ret = 99999
        for j in range(i + 1, len(T)):
            if x == S[j]:
                S[i], S[j] = S[j], S[i]
                ret = min(ret, 1 + self.util(S, T, i + 1))
                S[i], S[j] = S[j], S[i]
        return ret

    def solve(self, S, T):
        return self.util(S, T, 0)

ob = Solution()
S = "kolkata"
T = "katloka"
print(ob.solve(S, T))

補足ポイント

Pythonの文字列はイミュータブル(変更不可)なため、list() でリストに変換してから要素を入れ替えています。また、再帰の中で毎回リスト変換を行っている点は非効率なので、実際に使う場合は呼び出し前に一度だけ変換しておくとパフォーマンスが向上します。

入力

"kolkata", "katloka"

出力

3

まとめ

このアルゴリズムは、各位置ごとに必要な文字を探して入れ替えを試み、バックトラッキングによって全パターンの中から最小手数を見つけるシンプルな手法です。文字列の長さを n とすると計算量は O(n!) 程度になるため、短い文字列向けの解法である点には注意しましょう。