Count Anagrams

Count Anagrams

What is this problem about?

The Count Anagrams interview question asks you to find the number of ways to rearrange a given string (which contains words separated by spaces) such that each word is an anagram of the original word. You only rearrange characters within each word; you do not change the order of the words themselves. You need to return the answer modulo 10^9 + 7.

Why is this asked in interviews?

MathWorks uses the Count Anagrams coding problem to test your knowledge of permutations of multi-sets and modular inverse. It’s a "Hard" problem because it involves complex formulas: n! / (n1! * n2! * ... * nk!), where ni is the frequency of each distinct character. You must perform division in modular arithmetic, which requires Fermat's Little Theorem.

Algorithmic pattern used

This problem uses Combinatorics / Number Theory.

1. Split the string into words.
2. For each word, count the frequency of each character.
3. Calculate the number of permutations: factorial(total_length) / product of factorial(frequencies).
4. Since we are working modulo 10^9 + 7, the division is performed by multiplying by the Modular Multiplicative Inverse.
5. Multiply the results for all words together.

Example explanation

Input: "too hot"

1. Word "too": Length 3. Frequencies: t:1, o:2.
   • Permutations = 3! / (1! * 2!) = 6 / 2 = 3. (too, oto, oot)
2. Word "hot": Length 3. Frequencies: h:1, o:1, t:1.
   • Permutations = 3! / (1! * 1! * 1!) = 6.
3. Total = 3 * 6 = 18.

Common mistakes candidates make

• Ignoring Duplicates: Using n! without dividing by the factorials of character frequencies.
• Standard Division: Using regular division / with modulo, which is mathematically incorrect. You must use the modular inverse.
• Pre-calculation: Not pre-calculating factorials, leading to an O(N^2) solution instead of O(N).

Interview preparation tip

Memorize the modular inverse formula: a^(p-2) % p where p is prime. This is essential for any combinatorics problem involving division and modulo.