Pythonで文字列の文字を使って作れる一意な回文の数を数えるプログラム

文字列 s が与えられたとき、その文字列に含まれるすべての文字を使って作成できる一意な回文の数を求めます。答えが非常に大きくなる可能性があるため、結果は 10⁹ + 7 で割った余りを返します。

例えば、入力が s = "xyzzy" の場合、出力は 2 になります。「zyxyz」と「yzxzy」という2種類の回文を作ることができるためです。

解法の考え方

回文は左右対称の構造を持っています。つまり、文字列の左半分の並び方が決まれば、右半分は自動的に決まります。この性質を利用して、以下の手順で問題を解きます。

• m = 10^9 + 7:剰余を取るための値を設定します。
• char_freq:文字列 s の各文字とその出現回数を記録したマップを作成します。
• odd = 0:奇数回出現する文字の数をカウントする変数を初期化します。
• 各文字 k とその出現回数 v について、v が奇数の場合は odd を 1 増やします。
• odd > 1 の場合、奇数回出現する文字が複数あるため回文が成立せず、0 を返します。
• half_length:文字列の長さを 2 で割った商(左半分の長さ)を求めます。
• res:half_length の階乗を計算します。
• dividor = 1:各文字について、出現回数を 2 で割った商の階乗を掛け合わせます。
• 最後に (res ÷ dividor) mod m を返します。

この方法が正しい理由は、左半分の並べ替えの総数から、同じ文字同士を入れ替えた場合の重複を階乗で割り引くことで、それがそのまま一意な回文の総数になるからです。

実装例

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

from math import factorial

class Solution:
    def solve(self, s):
        m = (10**9+7)
        char_freq = {}
        for c in s:
            char_freq[c] = char_freq.get(c, 0) + 1

        odd = 0
        for k, v in char_freq.items():
            if v % 2 == 1:
                odd += 1
        if odd > 1:
            return 0

        half_length = len(s)//2
        res = factorial(half_length)
        dividor = 1
        for k, v in char_freq.items():
            dividor *= factorial(v//2)

        return (res//dividor) % m

ob = Solution()
print(ob.solve("xyzzy"))

入力

"xyzzy"

出力

2

まとめ

このアルゴリズムは、まず各文字の出現回数を調べて回文が成立するかどうかを判定し、成立する場合は左半分の順列の数を階乗によって計算することで、一意な回文の総数を効率よく求めます。文字列の長さを n とすると、頻度の集計は線形時間で行えるため、全体として非常に高速に動作します。