Pythonで指定された文字列の文字から作成できるサイズkの回文の総数を数える方法

アルファベット文字からなる文字列 s と整数 k が与えられたとします。このとき、s に含まれる文字だけを使って構成できる「長さ k の回文」の総数を求めます。同じ文字は何度でも繰り返し使用して構いません。

例えば、入力が s = "xy"、k = 4 の場合、出力は 4 になります。これは、作成できる回文が [xxxx, yyyy, xyyx, yxxy] の 4 通りだからです。

解法のアプローチ

この問題は、回文の性質を利用すると非常にシンプルに解けます。長さ k の回文では、前半部分が決まれば後半部分は自動的に鏡像として決まるため、自由に選べるのは前半の文字だけです。さらに k が奇数の場合は、中央の 1 文字も独立に選ぶことができます。

具体的には、次の手順で計算します。

• n := k ÷ 2 の商（小数点以下切り捨て）
• x := 文字列 s に含まれる一意な文字の種類数
• x^(n + k mod 2) を返す

各位置に使える文字は x 種類あるため、選択が必要な位置の数（n + k mod 2）だけ累乗すれば答えが得られます。

実装例

理解を深めるために、Python での実装を見てみましょう。

class Solution:
    def solve(self, s, k):
        n = k // 2
        return len(set(s)) ** (n + k % 2)

s = "xy"
k = 4
ob = Solution()
print(ob.solve(s, k))

入力

"xy", 4

出力

4

計算量について

このアルゴリズムの時間計算量は O(len(s))（set の生成に必要な分）であり、空間計算量も O(len(s)) です。回文を実際に列挙するわけではなく数式で総数を求めるため、k が大きくなっても高速に動作する点が大きなメリットです。