Python 3.xのCounter()関数で2つの文字列をアナグラムにする最小削除文字数を求める方法

本記事では、Python 3.xのCounter()関数を使って、2つの文字列をアナグラムの関係にするために削除すべき最小の文字数を求める方法を解説します。入力文字列からは任意の文字を削除できるものとし、アナグラムを実現するために何文字削除すればよいのかを、アルゴリズムと実装例を交えて具体的に見ていきます。

アナグラムとは

2つの文字列が互いにアナグラムであるとは、同じ種類の文字（アルファベット）を任意の順序で含んでいる状態を指します。たとえば「listen」と「silent」のように、構成する文字の種類と個数が完全に一致していれば、並び順が異なっていてもアナグラムとみなされます。

Counter()メソッドについて

Counter()は、Pythonの標準ライブラリであるcollectionsモジュールに用意されているクラスです。使用する際は、あらかじめcollectionsモジュールをインポートしておく必要があります。

collections.Counterはdictのサブクラスであり、インタプリタ側で自動的に文字の出現回数をカウントしてくれます。そのため、部分文字列を手作業で生成したり、アナグラムかどうかを一つずつ確認したりするような面倒な処理は不要になります。

アルゴリズム

1. collectionsモジュールのCounter(inp_str)を使い、入力文字列を
   「文字をキー、出現頻度を値」とする辞書型に変換する。
2. 変換した2つの辞書それぞれのキーの総数を数え、さらに両辞書に
   共通して存在するキーの数を数える。
3. 共通キーが1つも存在しない場合、すべての文字が異なることを意味するため、
   両方の入力文字列から（両辞書の長さの合計）文字を削除する必要がある。
4. 共通キーが存在する場合は、（max(両辞書の長さ) − 共通キーの数）が
   削除すべき文字数となる。

実装例

# 2つの文字列をアナグラムにする
from collections import Counter

def convertAnagram(str_1, str_2):
    # 文字列を辞書型に変換
    dict_1 = Counter(str_1)
    dict_2 = Counter(str_2)
    keys_1 = dict_1.keys()
    keys_2 = dict_2.keys()
    # 両方のキーリストのキー数をカウント
    count_1 = len(keys_1)
    count_2 = len(keys_2)
    # 共通キーを見つけるためにキーをセットに変換
    set_1 = set(keys_1)
    commonKeys = len(set_1.intersection(keys_2))
    if (commonKeys == 0): # 共通要素なし＝すべて異なる文字
        return (count_1 + count_2)
    else: # 入力時点で一部の要素が一致している
        return (max(count_1, count_2) - commonKeys)

str_1 = 'Tutorials'
str_2 = 'sTutalori'
str_3 = 'Point'
print(convertAnagram(str_1, str_2))
print(convertAnagram(str_3, str_2))

実行結果

0
6

最初の例では「Tutorials」と「sTutalori」がすでにアナグラムの関係にあるため、削除が必要な文字数は0となります。一方、「Point」と「sTutalori」を比較した場合は、6文字の削除が必要であることがわかります。

まとめ

本記事では、PythonのCounter()関数を活用して、2つの文字列をアナグラムの関係にするために必要な最小削除文字数を求める方法を学びました。文字の出現頻度を辞書として管理し、共通キーの数を比較するだけで効率的に計算できる点が大きなポイントです。文字列処理やアルゴリズムの学習に役立つテクニックなので、ぜひ実際にコードを動かして試してみてください。