Chương trình đếm số palindromes duy nhất mà chúng ta có thể thực hiện bằng cách sử dụng các ký tự chuỗi trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số palindromes riêng biệt mà chúng ta có thể tạo ra bằng cách sử dụng tất cả các ký tự. Nếu câu trả lời là rất lớn thì hãy sửa đổi kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là s =​​"xyzzy", thì đầu ra sẽ là 2, vì chúng ta có thể tạo "zyxyz" và "yzxzy"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m =10 ^ 9 + 7

• char_freq:=một bản đồ chứa từng ký tự của s và tần số của chúng

• lẻ:=0

• đối với mỗi ký tự k và tần số v trong char_freq, thực hiện

  • nếu v mod 2 là 1 thì

    • lẻ:=lẻ + 1

• nếu lẻ> 1 thì

  • trả về 0

• Half_length:=thương số của (cỡ s) / 2

• res:=giai thừa của half_length

• số chia:=1

• đối với mỗi ký tự k và tần số v trong char_freq, thực hiện

  • dividor:=dividor * giai thừa của (thương của v / 2)

• return (thương số của res / dividor) mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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"))

Đầu vào

"xyzzy"

Đầu ra

2