Game Of Thrones – II  | HackerRank Solution [Hard]

Problem

The king has many words. For each given word, he needs to find out the number of palindrome anagrams of the string. As the number of anagrams can be large, the king needs the number of anagrams % (10⁹+ 7).

HackerRank Problem Link

Input

A single line which contains the input string.

Output

A single line which contains the number of anagram strings which are palindrome % (10⁹ + 7).

Constraints

• 1<= length of string <= 10^5
• Each character of the string is a lowercase alphabet.

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 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(10⁹+ 7), we could use the modular multiplicative inverse discussed in this post.

Code Implementation

//
//  main.cpp
//  Game of Thrones II
//
//  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)