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

はじめに

小文字からなる文字列の配列が与えられたとき、互いにアナグラムの関係にある文字列からなる「最大のサブセット」のサイズを求めるのが本記事の課題です。
アナグラムとは、ある文字列が別の文字列の並べ替え（文字の順番の入れ替え）によって作られる関係のことです。たとえば、「python」と「typhon」はアナグラムの関係にあります。

Pythonでは、collectionsモジュールのCounter()メソッドを活用することで、この問題をシンプルかつ効率的に解くことができます。

アルゴリズムの手順

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

なぜソートが有効なのか

アナグラム同士の文字列は構成する文字が完全に一致しているため、それぞれの文字列をソートすると必ず同じ文字列になります。この性質を利用し、ソート後の文字列をキーとしてCounterでグループ化することで、同じキーを持つ文字列の数、すなわちアナグラムのグループのサイズが分かります。あとはmax(newstr1.values())で最大のグループサイズを取得するだけです。

サンプルコード

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」が1つのアナグラムグループ、「rty」「ytr」「ytr」「ytr」が4つの要素を持つもう1つのグループとなり、最大のサブセットサイズは4と出力されます。

まとめ

文字列をソートして正規化し、Counterで出現頻度を集計するというアプローチにより、アナグラムのグループ分けを直感的かつ短いコードで実現できます。計算量は文字列の長さをL、単語数をNとするとO(N・L log L)程度に収まり、実用上も十分高速です。