Solution: Count Anagrams

Statement

You are given a string, s, containing one or more words separated by a single space. Your task is to count and return the number of distinct anagrams of the entire string s. As the answer may be very large, return it modulo $10^9$ + $7$, i.e., return the remainder when the answer is divided by $10^9$ + $7$.

Note: An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once. For example, “listen” is an anagram of “silent”. Similarly, a string t is an anagram of string s if the ith word of t is a permutation of the ith word of s. For example, “silent era” is an anagram of “listen ear”, but "sline tear" is not.

Constraints:

• $1 \leq$ s.length $\leq 10^3$

• s consists of lowercase English letters and spaces ' '.

• There is only a single space between consecutive words.

Solution

An anagram of the entire string means that each word can be rearranged independently, but the order of the words stays the same. This implies that we can find a string’s total number of distinct anagrams by calculating how many valid permutations exist for each word. The number of permutations for each word depends on its length and the frequency of its letters. By multiplying all words’ permutations, we get the total number of distinct anagrams for the whole string.

The total permutations of a word with length $n$ (if all letters are unique) can be calculated using $n!$. But, if there are duplicate characters, the formula is adjusted by dividing $n!$ by the factorial of the frequency of each character to avoid double-counting. The final formula for counting all the valid permutations of a word while accounting for duplicate characters is:

$Unique~~permutations~~of~~a~~word$= $\frac{n!}{c_1! \times c_2! \times \dots}$ ...