Simple python3 solution with explanation | 199 ms - faster than 90.13% solutions
Approach\n Describe your approach to solving the problem. \n\nCalculate for "too hot":\n1. split into words: "too", "hot"\n2. answer is \prod_{i = 0}^n calc(wor
# Approach\n<!-- Describe your approach to solving the problem. -->\n\nCalculate for `"too hot"`:\n1. split into words: `"too"`, `"hot"`\n2. answer is $$\\prod_{i = 0}^n calc(word_i) = \\prod_{i = 0}^n \\frac{m_i!}{\\prod{k_{ij}!}}$$\nwhere $$m_i$$ is length of i-word and $$k_{ij}$$ is number of repetitions of unique chars in i-word\nfor example: $$\\frac{3!}{1! \\cdot 2!} \\cdot \\frac{3!}{1! \\cdot1! \\cdot1!} = \\frac{6 \\cdot 6}{2} = 18$$\n\n3. count all $m_i$ (with positive counter) and $k_{ij}$ (with negative counter)\nfor example: `{3: 2, 2: -1, 1: -4}`\n4. for all $m_i$ and $k_{ij}$ count number of prime numbers in factorials it total\nfor example: `{3: 2, 2: 1}`\n5. multiply all $$(prime^{power}) \\space \\% \\space modulo$$\n\n# Complexity\n- Time complexity: $$O(m \\cdot \\log(\\log(m)) + n \\cdot m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n \\cdot m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nwhere `n = words.length`, `m = max(word[i].length)`\n\n# Code\n``` python3 []\nclass Solution:\n    def countAnagrams(self, s: str) -> int:\n        def get_primes(max_number):\n            primes = [2]\n            sieve = [True] * (max_number + 1)\n            for i in range(3, max_number + 1, 2):\n                if sieve[i]:\n                    primes.append(i)\n                    for k in range(i ** 2, max_number + 1, 2 * i):\n                        sieve[k] = False\n            return primes\n\n        words = s.split()\n        max_number = max(len(word) for word in words)\n        PRIMES = get_primes(max_number)\n        \n        def get_primes_number(value):\n            result = Counter()\n            for prime in PRIMES:\n                if prime > value:\n                    break\n                prime_in_pow = prime\n                while prime_in_pow <= value:\n                    result[prime] += value // prime_in_pow\n                    prime_in_pow *= prime\n            return result\n\n        factorials = Counter()\n        for word in words:\n            factorials[len(word)] += 1\n            for value, value_cnt in Counter(Counter(word).values()).items():\n                factorials[value] -= value_cnt\n        \n        all_primes = Counter()\n        for value, value_cnt in factorials.items():\n            if value_cnt == 0:\n                continue\n            for prime, prime_cnt in get_primes_number(value).items():\n                all_primes[prime] += value_cnt * prime_cnt\n\n        modulo = 1_000_000_007\n        result = 1\n        for prime, pow_ in all_primes.items():\n            current = pow(prime, pow_, modulo)\n            result = (result * current) % modulo\n        return result\n```
['Hash Table', 'Math', 'Combinatorics', 'Counting', 'Python3']