Pythonで単語リストから最大のアナグラムグループを見つける方法

問題の概要

文字列のリスト words が与えられたとき、互いにアナグラム（並べ替えた文字列）の関係にある単語同士をすべてグループ化し、その中で最も大きなグループのサイズを返すことを考えます。

アナグラムとは、同じ文字を構成要素として持ち、文字の順序だけが異なる文字列のことです。たとえば「xyz」「zyx」「yzx」は、それぞれの文字の出現回数が同一であるため、同じアナグラムグループに属します。

例として、入力が words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"] の場合を考えてみましょう。このとき「xy」と「yx」が1つのグループ、「xyz」「zyx」「yzx」が3つの単語からなるもう1つのグループとなり、「wwwww」は他に仲間がないため単独です。最大のグループは ["xyz", "zyx", "yzx"] なので、出力は 3 になります。

解決のアプローチ

アナグラムを見分ける鍵となるのは「文字を辞書順にソートすると、アナグラム同士は必ず同じ文字列になる」という性質です。これを利用して、以下の手順で解くことができます。

• lookup: ソート済み文字列をキーとする空の辞書（マップ）を用意する
• res: 最大グループサイズを記録する変数で、初期値は 0
• リスト内の各単語 i について以下を繰り返す
  • 単語を辞書順にソートし、結合してキー p を作る
  • p がすでに lookup に存在すればカウントを1増やし、なければ 1 から始める
  • res と lookup[p] の大きい方を res に代入する
• 最後に res を返す

この方法では各単語につきソートのコスト O(K log K)（K は単語の長さ）だけで処理でき、全体として効率的にグループ化できます。

実装例

class Solution:
    def solve(self, words):
        lookup = {}
        res = 0
        for i in words:
            p = "".join(sorted(i))
            lookup[p] = lookup.get(p, 0) + 1
            res = max(res, lookup[p])
        return res

ob = Solution()
words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]
print(ob.solve(words))

入力

["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]

出力

3

コードのポイント

この実装で重要なのは、Python の dict.get() メソッドを使っている点です。lookup.get(p, 0) により、キーが存在しない場合でもエラーにならずデフォルト値の 0 を返すため、カウント処理を簡潔に書けます。

また、"".join(sorted(i)) という一行で「文字列のソート → 再結合」を行っており、これがアナグラム判定用の正規化キーとして機能します。同じキーを持つ単語は必ず同じアナグラムグループに属するため、辞書の値の最大値がそのまま答えになります。