Pythonで文字列のアナグラムが回文になるかどうかを判定する方法

文字列 s が与えられたとき、その文字列のアナグラム（並べ替え）の中に回文となるものが存在するかどうかを判定する問題を考えてみましょう。

例えば、入力が s = "aarcrec" の場合、この文字列を並べ替えると "racecar" という回文を作ることができるため、出力は True になります。

解法の考え方

回文の重要な性質として、「各文字の出現回数のうち、奇数回出現する文字は最大でも1種類まで」というルールがあります。これは、回文では左半分と右半分が鏡像の関係になるためです。

• 偶数長の回文：すべての文字が偶数回出現する
• 奇数長の回文：ちょうど1つの文字だけが奇数回出現し、それが中央に配置される

したがって、以下の手順で判定できます。

• freq := 各文字とその出現回数を格納するマップ（辞書）を用意する
• odd_count := 0 で初期化する
• freq のすべての値 f について繰り返す
  • f が奇数の場合、odd_count を1増やす
• odd_count が 1 より大きい場合は False を返す
• それ以外の場合は True を返す

実装例

以下がPythonでの実装例です。

from collections import defaultdict
def solve(s):
    freq = defaultdict(int)
    for char in s:
        freq[char] += 1
    odd_count = 0
    for f in freq.values():
        if f % 2 == 1:
            odd_count += 1
    if odd_count > 1:
        return False
    return True
s = "aarcrec"
print(solve(s))

入力

"aarcrec"

出力

True

コードの解説

defaultdict(int) を使うことで、まだ存在しないキーにアクセスした際も自動的に初期値 0 が設定されるため、文字ごとの出現回数を簡潔にカウントできます。その後、出現回数が奇数である文字の数を数え、それが2つ以上あれば回文を構成できないため False を返します。

このアルゴリズムの計算量は、文字列の長さを n とすると O(n) となり、非常に効率的です。