Pythonで文字列を並べ替えて回文を作成できるかどうかを判定する方法

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

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

考え方

回文になるための条件はシンプルです。各文字の出現回数に着目すると、以下のようになります。

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

つまり、「奇数回出現する文字の種類数が1以下」であれば、並べ替えて回文を作成できます。

アルゴリズムの手順

1. 頻度カウント用の配列 freq をサイズ256（ASCII文字対応）で0初期化します。
2. 文字列 s の各文字について、freq 配列内の出現回数を1ずつ増やします。
3. odd_count を0で初期化し、freq 配列を走査して奇数回出現する文字をカウントします。
4. odd_count が1を超えた時点で False を返します。
5. 最後まで問題なければ True を返します。

実装例

size = 256
def solve(s):
    freq = [0] * size
    for i in range(len(s)):
        freq[ord(s[i])] += 1
    odd_count = 0
    for i in range(size):
        if freq[i] % 2 == 1:
            odd_count += 1
        if odd_count > 1:
            return False
    return True

s = "aarcrce"
print(solve(s))

入力

"aarcrce"

出力

True

計算量

このアルゴリズムの時間計算量は O(n)（nは文字列の長さ）、空間計算量は O(1)（固定サイズ256の配列を使用）となります。非常に効率的な手法です。

まとめ

文字の出現頻度をカウントし、奇数回出現する文字が高々1種類であることを確認するだけで、回文への並べ替え可能性を判定できます。collections.Counter を使えば、さらに簡潔に記述することも可能です。