Anagram Problem [Hard]

Problem

Alansh has several words. For each given word, he wants to find the number of palindromic anagrams of that word. Since, the number of anagrams would be large, he needs the number of anagrams modulo (10⁹+ 7).

Input

A lowercase alphabetical string.

Output

A single line which contains the number of palindromic anagrams % (10⁹ + 7).

Constraints

• 1<= length of string <= 10⁵

Sample Input

aaabbbb

Sample Output

3

Explanation
Three palindrome permutations of the given string are abbabba , bbaaabb and bababab.

Solution

Consider a string of length n. To find its palindromic permutations, we could consider a substring of length n/2 having half of number of each character present in the original string. For example:
if string s = “ababbb”, then its half substring would be sub = “abb”. So all the permutations of the string sub would be palindromic with the other half which is same as sub ie “abb”. Now, to find the number of permutations of sub (“abb”), we could use the following formula:

Number of permutation for a string of length n having all unique characters is n!.

If some of them are repeating, then formula is n!/ (k1!*k2!*k3!...) where k[i] is the number of times a char k_i appears in the string.

To calculate n!/(k1!*k2!*k3!...) mod (109+ 7), we could use the modular multiplicative inverse discussed in this post.

Code Implementation

//
//  main.cpp
//  Anagram Problem
//
//  Created by Himanshu on 18/02/22.
//

#include<iostream>
#include<string>
#define mod 1000000007
using namespace std;
typedef long long ll;


void precompute (int n, ll fact[], ll invFact[], ll inv[]) {
    fact[0] = 1;
    
    for (int i=1; i<= n; i++) {
        fact[i] = (fact[i-1]*i)%mod;
    }
    inv[1] = 1;
    
    for (int i=2; i<= n; i++) {
        inv[i] = ((mod - (mod/i))*inv[mod%i])%mod;
    }
    
    invFact[0] = invFact[1] =1;
       
    for (int i=2; i<= n; i++) {
        invFact[i] = (invFact[i-1]*inv[i])%mod;
    }
}


int main() {
    ll ans;
    string s;
    int *alph = new int[26]();
    cin>>s;
    
    int n = (int) s.size();
    ll *fact = new ll[n/2 + 1]();
    ll *inv = new ll[n/2 + 1]();
    ll *invFact = new ll[n/2 + 1]();
    
    for (int i=0; i<n; i++) {
        alph[s[i] - 'a']++;
    }
    
    precompute(n/2, fact, invFact, inv);
    
    ans = fact[n/2];
    
    for (int i=0; i<=25; i++) {
        ans = (ans*invFact[(alph[i]/2)])%mod;
    }
    
    cout<<ans<<endl;
    
    return 0;
}

Time Complexity: O(n)