Pythonでアナグラム単語の最大サブセットサイズを求める方法

小文字からなる単語のリストが与えられたとき、互いにアナグラムの関係にある文字列からなる最大サブセットのサイズを求めるのが本記事の課題です。

アナグラムとは、一方の文字列がもう一方の文字列の並べ替え（文字の順番を入れ替えたもの）になっている関係を指します。たとえば、「python」と「typhon」はアナグラムです。

Pythonでは、標準ライブラリのcollections.Counter()メソッドを活用することで、この問題を非常に効率的に解決できます。

アルゴリズムの手順

ステップ1：スペース区切りの入力文字列を単語ごとに分割する。
ステップ2：リスト内の各文字列を文字順にソートする。
ステップ3：Counterメソッドで辞書を作成し、ソート済み文字列をキー、出現頻度を値として格納する。
ステップ4：max関数を使って頻度の最大値を取得する。

実装コード

# アナグラム単語の最大サブセットのサイズを求める関数
from collections import Counter

def largestana(str1):
    # スペース区切りの入力文字列を単語ごとに分割
    str1 = str1.split(" ")

    # リスト内の各文字列をソートする
    for i in range(0, len(str1)):
        str1[i] = ''.join(sorted(str1[i]))

    # Counterメソッドで辞書を作成
    # キー：ソート済み文字列　値：出現頻度
    newstr1 = Counter(str1)

    # 頻度の最大値を取得して表示
    print("アナグラム単語の最大サブセットのサイズ ::>", max(newstr1.values()))

# ドライバープログラム
if __name__ == "__main__":
    str1 = input("文字列を入力してください ::>")
    largestana(str1)

実行結果

文字列を入力してください ::> qwe ewq rty ytr ytr ytr
アナグラム単語の最大サブセットのサイズ ::> 4

仕組みの解説

このプログラムのポイントは、各単語を文字ごとにソートしている点にあります。アナグラム同士の文字列は、構成する文字がまったく同じであるため、ソートを行うと必ず同一の文字列になります。上記の例では、「qwe」「ewq」はどちらもソートすると「eqw」になり、「rty」「ytr」はすべて「rty」になります。その結果、頻度は「eqw」が2回、「rty」が4回となり、最大値の4が答えとして出力されます。

計算量は、n個の単語それぞれの長さをkとすると O(n・k log k) となり、Counterによる集計は O(n) で処理されるため、実用上十分高速なアルゴリズムです。