Pythonで文字列文字を使用して作成できる一意の回文の数をカウントするプログラム

文字列sがあるとすると、すべての文字を使用して生成できる個別の回文の数を見つける必要があります。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します。

したがって、入力がs ="xyzzy"の場合、"zyxyz"と"yzxzy"を作成できるため、出力は2になります

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7

• char_freq：=sの各文字とその頻度を保持するマップ

• 奇数：=0

• char_freqの各文字kと頻度vについて、実行します

  • v mod 2が1の場合、

    • 奇数：=奇数+ 1

• 奇数>1の場合、

  • 0を返す

• half_length：=（sのサイズ）の商/ 2

• res：=half_lengthの階乗

• 除算器：=1

• char_freqの各文字kと頻度vについて、実行します

  • dividor：=dividor *（v / 2の商）の階乗

• return（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