【Python】文字の入れ替え操作で2つの文字列を一致させられるか判定する方法

問題の概要

同じ長さの小文字のみで構成された2つの文字列 s と t が与えられます。s から1文字、t から1文字を選んで入れ替える(スワップする)操作を、好きな回数だけ繰り返せるとします。このとき、2つの文字列を完全に同じにできるかどうかを判定するのが本記事のテーマです。

例えば、入力が s = "abcd"、t = "cdab" の場合、出力は True になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• s と t を連結した文字列に含まれる各文字の出現回数(fre)を集計します。
• fre の各値(cnt)について次を確認します。
  • cnt を2で割った余りが1(つまり奇数)の場合は False を返します。
• すべての文字数が偶数であれば、True を返します。

なぜこれで判定できるのか

ポイントは「スワップ操作を何度行っても、全体としての文字の出現頻度は変わらない」という点です。ある文字の合計出現回数が偶数であれば、その文字を s 側と t 側にちょうど半分ずつ振り分けられるため、両者を一致させることが可能です。逆に、たった一つの文字でも奇数回出現していれば、2つの文字列を完全に一致させることはできません。

実装例

Python の標準ライブラリ collections.Counter を使えば、文字ごとの出現回数を簡単に集計できます。以下が実際のコードです。

from collections import Counter

def solve(s, t):
    fre = Counter(s + t)

    for cnt in fre.values():
        if cnt % 2:
            return False

    return True

s = "abcd"
t = "cdab"
print(solve(s, t))

入力

"abcd", "cdab"

出力

True

計算量について

時間計算量は O(n)(n は文字列の長さ)です。Counter の構築に文字列の長さに比例した時間がかかりますが、小文字は最大26種類しかないため、頻度チェックのループ部分は定数時間とみなせます。空間計算量も O(n) であり、非常に効率的な解法といえます。