【Python】文字列を並べ替えて回文を作れるかどうかを判定する方法

問題の概要

文字列 s が与えられたとき、その文字を並べ替えることで回文（前から読んでも後ろから読んでも同じになる文字列）を作ることができるかどうかを判定します。

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

解決のアプローチ

文字を自由に並べ替えて回文を形成できる条件は、「奇数回出現する文字が最大1種類であること」です。これは次のように考えられます。

• 文字列の長さが偶数の場合：すべての文字が偶数回出現する必要があります。
• 文字列の長さが奇数の場合：ちょうど1つの文字だけが奇数回出現し、その文字が中央に配置されます。

この性質を利用すると、以下の手順で問題を解くことができます。

• freq：文字列 s 内の各文字とその出現回数を格納するマップを作成する
• odd_count := 0（奇数回出現する文字の種類数をカウント）
• freq のすべての値 i について以下を繰り返す：
  • i が奇数の場合、odd_count を 1 増やす
  • odd_count が 1 を超えた時点で False を返す
• ループが完了すれば True を返す

実装例

以下のコードで実際の実装を確認してみましょう。

from collections import defaultdict

def solve(st):
    freq = defaultdict(int)
    for char in st:
        freq[char] += 1
    odd_count = 0
    for i in freq.values():
        if i % 2 == 1:
            odd_count += 1
        if odd_count > 1:
            return False
    return True

s = "raaecrc"
print(solve(s))

入力

"raaecrc"

出力

True

計算量の分析

時間計算量：O(n) ― 文字列を一度走査して各文字の出現回数を数え、その後頻度マップを走査します（n は文字列の長さ）。
空間計算量：O(k) ― k は文字列に含まれる異なる文字の種類数です。

まとめ

このアルゴリズムは、各文字の出現回数をカウントし、奇数回出現する文字が1種類以下であるかを確認するだけで、回文への並べ替え可否を効率的に判定できます。早期に False を返すことで無駄な計算も避けられます。