สมมติว่ามีสตริง s เราต้องหาจำนวนพาลินโดรมที่แตกต่างกันที่สามารถสร้างได้โดยใช้ตัวอักษรทั้งหมด หากคำตอบใหญ่มาก ให้มอดูลัสด้วย 10^9 + 7
เช่น ถ้าอินพุตคือ s = "xyzzy" ผลลัพธ์จะเป็น 2 เนื่องจากสามารถสร้าง "zyxyz" และ "yzxzy" ได้
ขั้นตอนการแก้ปัญหา
- m = 10^9+7
- char_freq := map เก็บตัวอักษรแต่ละตัวใน s และความถี่
- odd := 0
- สำหรับแต่ละตัวอักษร k และความถี่ v ใน char_freq ทำ
- ถ้า v mod 2 เท่ากับ 1 แล้ว odd := odd + 1
- ถ้า odd > 1 คืนค่า 0
- half_length := ผลหารของ (ขนาดของ s) / 2
- res := แฟกทอเรียลของ half_length
- dividor := 1
- สำหรับแต่ละตัวอักษร k และความถี่ v ใน char_freq ทำ
- dividor := dividor * แฟกทอเรียลของ (ผลหารของ 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"
เอาต์พุต
2
