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에 대해 수행
- 제수 :=제수 * 계승(v/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"