Count Anagrams, C++ Explained Solution With Complete Maths and Intuition
Upvote If Found Helpful !!!\n\n# Approach\n Describe your approach to solving the problem.  \nThe problem here is actually quite simple in terms of logic formul
***Upvote If Found Helpful !!!***\n\n# Approach\n<!-- Describe your approach to solving the problem. --> \nThe problem here is actually quite simple in terms of logic formulation. We can directly see that we just have to multiply the number of permutations of each word to get the total distinct number of anagrams. The problem comes up in finding the number of permutations. The number of permutations of a string is given by **P = (M!) / (K1! * K2! * K3! * ...)** where **M** is the length of the word and **K1, K2, K3 and so on** is the count of each type of character present in the word. In our case, we can have atmost 26 types of characters (**Alphabets**). The problem is easy if **K1, K2** etc. are relatively small like **1, 2** but factorial goes on increasing exponentially so its possible to get fractional values which in turn would create problem in storing in terms of double data type. So what do we do ???\n\nHere comes in **Modular Arithmatic**. Lets recall the concept of finding **nCr mod p**, where **n and r** are some values and **p is a large prime number**. The main concept is to find **(1 / r!) mod p**. We can see that this looks somewhat similar to our problem too **((1 / K1!) mod p)**. Lets say **r! = J, then we need to find inverse(J) mod p**. How do we get this inverse ? \n\nHere we bring in ***Euler\'s Theorum*** which states that for some **a, m, a^(phi(m)) is congruent to 1 mod m** if **a and m are relatively prime i.e gcd(a,m) = 1**. Here **phi(m)** is basically Euler\'s totient function which gives the count of numbers from 1 to m that are coprime to m. Now if **m** is a prime number like **10^9+7**, then **phi(m) = m-1**. Thus it reduces down to ***Fermat\'s Little Theorum = a^(m-1) : 1 mod m***. If we multiply **a^(-1)** on both sides, we get **a^(m-2) : a^(-1) mod m**, where **a^(-1) is actually inverse of a**. Thus we see that inverse of a is basically **a^(m-2)** which we can easily find using binary exponentiation in logarithmic time. With this we have solved our main problem. Rest goes just multiplying values and regularly taking mod with **10^9+7**. Implementation goes below :\n\n# Complexity\n- Time complexity: **O(N*log(mod))**, where **N** is the size of the string and **mod** is 1000000007. You can also see that in order to save our time, we have pre-calculated the factorials of all values.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(N)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    #define ll long long\n    ll mod = 1e9+7LL;\n    ll fact[100005] = {1LL}; \n    void initialize(){\n        for(ll i = 1LL; i <= 100000; i++){\n            fact[i] = (fact[i-1] * i) % mod;\n        }\n    }\n    ll binexp(ll x){\n        ll y = mod - 2LL, ans = 1LL;\n        while(y){\n            if(y & 1LL){\n                ans = (ans * x) % mod;\n            }\n            x = (x * x) % mod;\n            y >>= 1LL;\n        }\n        return ans;\n    }\n    int countAnagrams(string s) {\n        ios_base::sync_with_stdio(0);\n        initialize();\n        int n = s.size();\n        ll ans = 1LL,l = 0; vector<ll>c(26,0);\n        for(int i = 0; i < n; i++){\n            if(s[i] == \' \'){\n                ll val = fact[l];\n                for(ll j = 0; j < 26; j++){\n                    if(c[j]){\n                        val = (val * binexp(fact[c[j]])) % mod;\n                    }\n                    c[j] = 0LL;\n                }\n                ans = (ans * val) % mod;\n                l = 0;\n            }\n            else{\n                l++;\n                c[s[i]-\'a\']++;\n            }\n        }\n        ll val = fact[l];\n        for(ll j = 0; j < 26; j++){\n            if(c[j]){\n                val = (val * binexp(fact[c[j]])) % mod;\n            }\n            c[j] = 0LL;\n        }\n        ans = (ans * val) % mod;\n        return ans;\n    }\n};\n```
['Math', 'C++']