โปรแกรมนับจำนวนพาลินโดรมที่ไม่ซ้ำกันที่เราสร้างโดยใช้อักขระสตริงใน Python

สมมติว่าเรามีสตริง s เราต้องหาจำนวนพาลินโดรมที่ต่างกันที่เราสร้างได้โดยใช้อักขระทั้งหมด หากคำตอบมีขนาดใหญ่มาก ให้แก้ไขผลลัพธ์ด้วย 10^9 + 7

ดังนั้น หากอินพุตเป็น s ="xyzzy" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถสร้าง "zyxyz" และ "yzxzy"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม =10^9+7

• char_freq :=แผนที่ที่มีอักขระแต่ละตัวของ s และความถี่ของพวกมัน

• คี่ :=0

• สำหรับแต่ละอักขระ k และความถี่ v ใน char_freq ทำ

  • ถ้า v mod 2 เป็น 1 แล้ว

    • คี่ :=คี่ + 1

• ถ้าคี่> 1 แล้ว

  • คืนค่า 0

• half_length :=ผลหารของ (ขนาด s) / 2

• res :=factorial ของ half_length

• ตัวหาร :=1

• สำหรับแต่ละอักขระ k และความถี่ v ใน char_freq ทำ

  • ตัวหาร :=ตัวหาร * แฟกทอเรียลของ (ผลหารของ v/2)

• ผลตอบแทน (ผลหารของความละเอียด/ตัวหาร) 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