পাইথনে স্ট্রিং ক্যারেক্টার ব্যবহার করে ইউনিক প্যালিনড্রোমের সংখ্যা গণনা করার প্রোগ্রাম

মনে করুন একটি স্ট্রিং s আছে, আমাদের সারোহ ক্যারেক্টার ব্যবহার করে কতগুলো স্বতন্ত্র প্যালিনড্রোম তৈরি করা যায় সেটি খুঁজে বের করতে হবে। উত্তর যদি বড় হয় তবে 10⁹+৭ দিয়ে মড করুন।

উদাহরণস্বরূপ, s = "xyzzy" হলে আউটপুট হবে 2, কারণ "zyxyz" এবং "yzxzy" তৈরি করা যায়।

সমাধানের ধাপসমূহ

m = 10⁹+7
char_freq := s-এ থাকা প্রতিটি ক্যারেক্টার এবং তাদের ফ্রিকোয়েন্সি ধারণকারী ম্যাপ
odd := 0
প্রতিটি ক্যারেক্টার k এবং ফ্রিকোয়েন্সি v-এর জন্য char_freq-এ,
- যদি v mod 2 == 1, তবে
  - odd := odd + 1
যদি odd > 1, তবে
- 0 ফেরত দিন
half_length := len(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"