Count Anagrams — LeetCode 2514 Python Solution

The problem

You are given a string s containing one or more words. Every consecutive pair of words is separated by a single space ' '.

Example

Input

s = "too hot"

Output

18

Explanation

Some of the anagrams of the given string are "too hot", "oot hot", "oto toh", "too toh", and "too oht".

Python solution

class Solution:
    def countAnagrams(self, s: str) -> int:
        mod = 10**9 + 7
        ans = mul = 1
        for w in s.split():
            cnt = Counter()
            for i, c in enumerate(w, 1):
                cnt[c] += 1
                mul = mul * cnt[c] % mod
                ans = ans * i % mod
        return ans * pow(mul, -1, mod) % mod

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2514. Count Anagrams is filed here because LeetCode tags it Math and Combinatorics, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems