Pythonで文字列のすべての文字を使ってk個の回文を作成できるかどうかを判定する方法

問題概要

文字列 s と整数 k が与えられたとき、s に含まれるすべての文字を使って、ちょうど k 個の回文（前から読んでも後ろから読んでも同じになる文字列）を作成できるかどうかを判定します。

たとえば、入力が s = "amledavmel"、k = 2 の場合、「level」と「madam」という2つの回文を作成できるため、出力は True になります。

解法の考え方

回文の性質に注目すると、この問題は非常にシンプルに解けます。回文では、奇数回出現できる文字は最大で1種類だけです。したがって、文字列のすべての文字を k 個の回文に振り分けられる条件は、「奇数回出現する文字の種類数が k 以下であること」となります。

この方針に基づき、次の手順で判定を行います。

• d := 各一意な文字とその出現頻度を格納するマップ（Counter を使用）
• cnt := 0（奇数回出現する文字のカウント用変数）
• d の各キー（文字）について以下を繰り返します：
  • d[key] が奇数であれば、cnt を 1 増やします
  • cnt が k を超えた時点で、False を返します
• ループが最後まで完了すれば、True を返します

なお、コード内の d[key] & 1 はビット演算による奇数判定です。d[key] % 2 == 1 と書いても同じ意味になります。

実装例

from collections import Counter

class Solution:
    def solve(self, s, k):
        d = Counter(s)
        cnt = 0
        for key in d:
            if d[key] & 1:
                cnt += 1
            if cnt > k:
                return False
        return True

ob = Solution()
s = "amledavmel"
k = 2
print(ob.solve(s, k))

入力

"amledavmel", 2

出力

True

計算量

時間計算量は O(n)（n は文字列の長さ）です。文字列を一度走査して頻度を数え、その後は文字種の数だけループするため、非常に効率的です。空間計算量は出現する文字の種類数に依存し、英小文字のみの場合は O(1) とみなせます。