Problem statement

https://binarysearch.com/problems/Distinct-Palindromes/

Solution

First, check that we have no more than one odd frequency. Then use multinomial coefficients to find answer.

Complexity

It is O(n) for time and space.

Code

MOD, M = 10**9 + 7, 10**4
F = [1]*(M+1)
for i in range(1, M+1):
    F[i] = (F[i-1] * i) % MOD

I = [1]*M + [pow(F[M], MOD - 2, MOD)]
for i in range(M-1, 0, -1):
    I[i] = I[i+1]*(i+1) % MOD

class Solution:
    def solve(self, s):
        cnt = Counter(s)
        if sum(i%2 == 1 for i in cnt.values()) > 1: return 0
        vals = [x//2 for x in cnt.values()]
        ans = F[sum(vals)]
        for v in vals:
            ans = (ans * I[v]) % MOD
        return ans