Fast C++ soln | Maths explained | O(n) TC
Intuition\nFor a given string, the answer can be found separately for each word in the string and multiplying over all words (from fundamental counting principl
# Intuition\nFor a given string, the answer can be found separately for each word in the string and multiplying over all words (from fundamental counting principle)\n\nFor each word, again use the counting principle. For ex: given a word `abbccd`\nthe number of anagrams is the number of permutations of this string -\n$ n= 6 \\ \\ \\textrm{(length of the string)}$\n$freq(a) = 1 \\\\ \n freq(b) = 2 \\\\\n freq(c) = 2 \\\\\n freq(d) = 1\n$\n$ count = \\frac{6!}{1! \\times 2! \\times 2! \\times 1!}\n$\n\n# Approach\n\n\n1. split the given string into words. I have done this using [`std::stringstream`](https://cplusplus.com/reference/sstream/stringstream/stringstream/).\n2. For each word calculate the number of anagrams as follows -\n\n    1. find the frequency of each character in the word. Let it be denoted by $count(i)$ where $i$ is a character in the word\n    2. let $n$ be the length of this word\n    3. now the answer is \n    $$ans= \\frac{n!}{\\prod count(i)!}$$\n3. multiply the answer across all words.\n\nI have precalculated the factorial and its inverse using the following formulae -\n\n$ f(i) =f(i-1) \\times i$\n\nthe inverse is a direct result of [Fermat\'s Little Theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem)\n\n$$ x^{-1}  \\equiv x^{m-2}\\  \\textrm{mod}\\ m $$\n\nFurther-\n\n$f(i)^{-1} = (i \\times f(i-1))^{-1}$\n$ \\implies f(i)^{-1} =i^{-1} \\times f(i-1)^{-1} $\n$\\implies f(i-1)^{-1}=f(i)^{-1} \\times i $\n\n\n\n\n# Code\n```\nconst long long mod=1e9+7;\nusing ll=long long;\n\n// binary exponentiation\nll binpow(ll a, ll b, ll m)\n{\n\ta %= m;\n\tll res = 1;\n\twhile (b > 0)\n\t{\n\t\tif (b & 1) res = res * a % m;\n\t\ta = a * a % m;\n\t\tb >>= 1;\n\t}\n\treturn res;\n}\n// find modular multiplicative inverse \n// using fermat\'s little theorem\nll inv(ll a, ll m = mod) { return binpow(a, m - 2, m); }\n\nconst int N=(int)1e5;\nll fact[N+1];\nll inv_fact[N+1];\nvoid precalc()\n{\n    fact[0]=1;\n    for(int i=1;i<=N;i++)\n        fact[i]=(fact[i-1]*i)%mod;\n    inv_fact[N]=inv(fact[N]);\n    for(int i=N-1;i>=0;i--)\n        inv_fact[i]=(inv_fact[i+1]*(i+1))%mod;\n}\nclass Solution {\npublic:\n    Solution()\n    {\n        // call precalc only once across all testcases\n        precalc();\n    }\n    // get the answer for each word\n    int calc_for_word(const string&s)\n    {\n        // frequency array for each character \n        ll a[26]{};\n        for(auto &ch:s)\n        {\n            a[ch-\'a\']++;\n        }\n        ll ans=fact[s.size()];\n        for(int i=0;i<26;i++)\n        {\n            ans*=inv_fact[a[i]];\n            ans%=mod;\n        }\n        return ans;   \n    }\n    int countAnagrams(string str) {\n        std::stringstream ss(str);\n        string temp;\n        ll ans=1;\n        while(ss>>temp){\n            ans*=calc_for_word(temp);\n            ans%=mod;\n        }\n        return ans;\n    }\n};\n\n```\n\n# Complexity\n- Time complexity:\n    1. `precalc` - $O(n)$\n    2. `countAnagrams` - $O(n)$\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
['Math', 'Memoization', 'C++']