Chương trình đếm số palindrome duy nhất có thể tạo từ ký tự chuỗi trong Python

Cho chuỗi s, đếm số palindrome khác nhau có thể tạo ra sử dụng tất cả các ký tự. Kết quả lấy modulo 10^9 + 7.

Ví dụ

Đầu vào: s = "xyzzy".
Đầu ra: 2 (palindrome: "zyxyz" và "yzxzy").

Thuật toán

1. Đếm tần suất từng ký tự trong s.
2. Đếm số ký tự có tần suất lẻ (odd). Nếu odd > 1, trả về 0 (không thể tạo palindrome).
3. Tính half_length = len(s) // 2.
4. Số palindrome = factorial(half_length) / (product(factorial(v//2) for v in frequencies)) modulo 10^9+7.

Mã nguồn Python

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 v in char_freq.values():
            if v % 2 == 1:
                odd += 1
        if odd > 1:
            return 0
        half_length = len(s) // 2
        res = factorial(half_length)
        dividor = 1
        for v in char_freq.values():
            dividor *= factorial(v // 2)
        return (res // dividor) % m

ob = Solution()
print(ob.solve("xyzzy"))

Đầu vào / Đầu ra

Input: "xyzzy"
Output: 2