# Count Anagrams
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-anagrams)
Canonical: https://scaleengineer.com/dsa/problems/count-anagrams
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
You are given a string `s` containing one or more words. Every consecutive pair of words is separated by a single space `' '`.

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, `"acb dfe"` is an anagram of `"abc def"`, but `"def cab"` and `"adc bef"` are not.

Return _the number of **distinct anagrams** of_ `s`. Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**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".

**Example 2:**

**Input:** s = "aa"
**Output:** 1
**Explanation:** There is only one anagram possible for the given string.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters and spaces `' '`.
* There is single space between consecutive words.

# Approaches
## Approach 1: Direct Calculation
This approach directly translates the mathematical formula for permutations into code. For each word, it calculates the number of distinct permutations and multiplies this into a running total. The formula for permutations of a word of length `n` with character counts `c1, c2, ...` is `n! / (c1! * c2! * ... * ck!)`.

To handle the modulo arithmetic, division is replaced by multiplication with the modular multiplicative inverse. Since `10^9 + 7` is a prime number, we can use Fermat's Little Theorem to find the inverse of `a` as `a^(MOD-2) % MOD`. This requires a helper function for modular exponentiation (also known as power function).

Helper functions for `factorial`, `power`, and `modInverse` are created and called as needed for each word.
**Time:** O(N + W * L_max * log(MOD)), where N is the length of `s`, W is the number of words, and L_max is the maximum length of a word. Splitting takes O(N). For each of the W words, we might compute factorials up to L_max, taking O(L_max) time, and perform up to 26 modular inverse calculations, each taking O(log(MOD)). In the worst case where W is proportional to N (e.g., many short words), this approaches O(N * log(MOD)). · **Space:** O(N), where N is the length of the input string `s`. This space is primarily used to store the array of words after splitting the string.
**Pros:** Simple to understand and implement.; Does not require extra space for pre-computation tables.
**Cons:** Inefficient due to repeated calculations. The `factorial(k)` function may be called multiple times with the same input `k` for different words or different character counts.; Each call to `factorial(k)` takes `O(k)` time, which can be slow if words are long.
### Explanation
The core of this method is to process each word independently. We first split the input string `s` into words. Then, for each word, we calculate how many unique ways its letters can be rearranged.

The number of permutations for a single word is given by the multinomial coefficient formula. For a word of length `n`, with `k` unique characters appearing `c1, c2, ..., ck` times respectively, the number of permutations is `n! / (c1! * c2! * ... * ck!)`.

Since we need the result modulo `10^9 + 7`, we perform all calculations within this finite field. The division operation `a / b` becomes `(a * modInverse(b)) % MOD`. The modular inverse is calculated using modular exponentiation.

This approach computes the necessary factorials and their inverses on-the-fly for each word. While straightforward, it leads to redundant computations if the same factorial is needed for multiple words or character counts.

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int countAnagrams(String s) {
        String[] words = s.split(" ");
        long ans = 1;

        for (String word : words) {
            ans = (ans * calculatePermutations(word)) % MOD;
        }

        return (int) ans;
    }

    private long calculatePermutations(String word) {
        int len = word.length();
        long permutations = factorial(len);

        int[] counts = new int[26];
        for (char c : word.toCharArray()) {
            counts[c - 'a']++;
        }

        for (int count : counts) {
            if (count > 1) {
                long denominatorFact = factorial(count);
                long invDenominator = modInverse(denominatorFact);
                permutations = (permutations * invDenominator) % MOD;
            }
        }
        return permutations;
    }
    
    private long factorial(int n) {
        long res = 1;
        for (int i = 2; i <= n; i++) {
            res = (res * i) % MOD;
        }
        return res;
    }

    private long modInverse(long n) {
        return power(n, MOD - 2);
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Define a constant `MOD = 10^9 + 7`.
2. Implement a `power(base, exp)` function for modular exponentiation to calculate `(base^exp) % MOD` efficiently.
3. Implement a `modInverse(n)` function that uses the `power` function to find the modular multiplicative inverse: `power(n, MOD - 2)`.
4. Implement a `factorial(n)` function that calculates `n!` modulo `MOD` by iterating from 2 to `n`.
5. Split the input string `s` by spaces to get an array of words.
6. Initialize a variable `totalAnagrams` to 1.
7. Iterate through each `word` in the array:
    a. Determine the length of the word, `n`.
    b. Count the frequency of each character in the word.
    c. Calculate the number of permutations for the current word using the formula: `n! / (c1! * c2! * ...)`.
    d. The calculation in modulo arithmetic is: `permutations = factorial(n)`.
    e. For each character count `c` greater than 1, update the permutations: `permutations = (permutations * modInverse(factorial(c))) % MOD`.
    f. Multiply this result into the `totalAnagrams`: `totalAnagrams = (totalAnagrams * permutations) % MOD`.
8. Return `totalAnagrams`.

## Approach 2: Pre-computing Factorials
This approach improves upon the first one by avoiding re-computation of factorials. Since the maximum length of any word (and any character count) is bounded by the total length of the string `s`, we can pre-calculate all necessary factorials once at the beginning and store them in an array.

First, we create a `factorials` array and populate it such that `factorials[i] = i! % MOD`. This takes `O(N)` time, where `N` is the length of `s`.

Then, when processing each word, instead of calling a `factorial()` function, we can retrieve the pre-computed values from the array in `O(1)` time. We still need to compute the modular inverse for each denominator term (`fact[count]`) on-the-fly using the `power` function. This optimization eliminates the redundant `O(L)` work for factorial calculations inside the main loop.
**Time:** O(N + W * log(MOD)), where N is the length of `s` and W is the number of words. Pre-computation takes O(N). The main loop iterates W times. Inside the loop, frequency counting takes O(L) (summing to O(N) over all words), and we perform up to 26 `modInverse` calls, each taking O(log(MOD)). The total is dominated by pre-computation and the inverse calculations. · **Space:** O(N), where N is the length of `s`. We need O(N) for the words array and O(N) for the `fact` array.
**Pros:** More efficient than the direct approach by eliminating redundant factorial calculations.; Factorial lookups are O(1).
**Cons:** Still requires on-the-fly calculation of modular inverses for each denominator term, which involves the `power` function (`O(log MOD)`), making it slower than the fully pre-computed approach.; Requires O(N) extra space for the factorials table.
### Explanation
To optimize the previous approach, we identify that factorial values are often re-calculated. We can eliminate this redundancy with pre-computation. We create an array, say `fact`, of size `s.length() + 1`. We fill this array such that `fact[i]` stores the value of `i!` modulo `MOD`.

This pre-computation step is done once. The main logic then proceeds as before: split the string into words and calculate permutations for each. However, when we need a factorial `k!`, we simply look it up in our `fact` array at index `k`. This is an `O(1)` operation.

The modular inverses of the denominator factorials are still computed as needed. This means for each word, we still loop through its character counts and call the `modInverse` function, which in turn calls the `power` function.

```java
class Solution {
    private static final int MOD = 1_000_000_007;
    private long[] fact;

    public int countAnagrams(String s) {
        int n = s.length();
        precomputeFactorials(n);

        String[] words = s.split(" ");
        long ans = 1;

        for (String word : words) {
            ans = (ans * calculatePermutations(word)) % MOD;
        }

        return (int) ans;
    }

    private void precomputeFactorials(int n) {
        fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
    }

    private long calculatePermutations(String word) {
        int len = word.length();
        long permutations = fact[len];

        int[] counts = new int[26];
        for (char c : word.toCharArray()) {
            counts[c - 'a']++;
        }

        for (int count : counts) {
            if (count > 1) {
                long invDenominator = modInverse(fact[count]);
                permutations = (permutations * invDenominator) % MOD;
            }
        }
        return permutations;
    }
    
    private long modInverse(long n) {
        return power(n, MOD - 2);
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Define `MOD = 10^9 + 7`.
2. Pre-compute all factorials up to `s.length()` and store them in an array `fact`. `fact[i] = i! % MOD`.
3. Implement `power` and `modInverse` functions as in the previous approach.
4. Split the input string `s` into words.
5. Initialize `totalAnagrams` to 1.
6. Iterate through each `word`:
    a. Get the length `n` and count character frequencies `c`.
    b. Get the numerator `fact[n]` from the pre-computed table.
    c. For each character count `c > 1`, calculate the inverse of its factorial: `inv = modInverse(fact[c])`.
    d. Multiply the numerator by this inverse: `permutations = (permutations * inv) % MOD`.
    e. Update the total count: `totalAnagrams = (totalAnagrams * permutations) % MOD`.
7. Return `totalAnagrams`.

## Approach 3: Pre-computing Factorials and Inverse Factorials
This is the most efficient approach. It builds upon the second approach by pre-computing not only the factorials but also their modular inverses. This eliminates the need for any `power` function calls inside the main loop, making the calculation for each word extremely fast.

The process involves two pre-computation steps:
1.  Compute `fact[i] = i! % MOD` for `i` from 0 to `N`.
2.  Compute `invFact[i] = (i!)⁻¹ % MOD`. This is done by first calculating `invFact[N]` using the `power` function once. Then, we can find the other inverse factorials iteratively using the property `(k!)⁻¹ = ((k+1)!)⁻¹ * (k+1)`. We iterate from `N-1` down to 0 to populate the `invFact` array.

After this `O(N)` pre-computation, calculating the permutations for any word involves only array lookups and multiplications, which are `O(1)` operations. This makes the main loop very fast.
**Time:** O(N), where N is the length of `s`. The pre-computation of both `fact` and `invFact` takes O(N + log(MOD)). Processing all words takes O(N) because it's just frequency counting and lookups. The overall complexity is linear in the length of the string. · **Space:** O(N), where N is the length of `s`. We need O(N) for the words array, O(N) for `fact`, and O(N) for `invFact`.
**Pros:** Most efficient approach with the best time complexity.; All calculations for permutations after pre-computation are extremely fast (O(1) lookups).
**Cons:** Requires more space than other approaches due to storing two arrays (`fact` and `invFact`).; The pre-computation logic is slightly more complex.
### Explanation
The key to this optimal approach is to pre-calculate everything possible. The permutation formula `n! / (c1! * c2! * ...)` can be rewritten as `n! * (c1!)⁻¹ * (c2!)⁻¹ * ...` in modular arithmetic. This means we need factorials and their inverses.

We pre-compute two arrays:
1.  `fact`: `fact[i]` stores `i! % MOD`.
2.  `invFact`: `invFact[i]` stores `(i!)⁻¹ % MOD`.

Computing `fact` is straightforward. To compute `invFact` efficiently, we first compute the inverse of the largest factorial we need, `fact[N]`, using the `power` function. This takes `O(log MOD)`. Then, we use the recurrence `invFact[i] = invFact[i+1] * (i+1) % MOD` to compute the rest of the values in `O(N)` time by iterating backwards.

With both `fact` and `invFact` arrays ready, processing each word becomes a series of lookups. For a word of length `n` with character counts `c_i`, the number of permutations is `fact[n] * invFact[c1] * invFact[c2] * ... % MOD`. Each of these operations is `O(1)`.

```java
class Solution {
    private static final int MOD = 1_000_000_007;
    private long[] fact;
    private long[] invFact;

    public int countAnagrams(String s) {
        int n = s.length();
        precomputeFactorials(n);

        String[] words = s.split(" ");
        long ans = 1;

        for (String word : words) {
            ans = (ans * calculatePermutations(word)) % MOD;
        }

        return (int) ans;
    }

    private void precomputeFactorials(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;

        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[n] = power(fact[n], MOD - 2);
        for (int i = n - 1; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    private long calculatePermutations(String word) {
        int len = word.length();
        long permutations = fact[len];

        int[] counts = new int[26];
        for (char c : word.toCharArray()) {
            counts[c - 'a']++;
        }

        for (int count : counts) {
            if (count > 1) {
                permutations = (permutations * invFact[count]) % MOD;
            }
        }
        return permutations;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Define `MOD = 1_000_000_007`.
2. Pre-compute factorials up to `s.length()` in an array `fact`.
3. Pre-compute the modular inverse of each factorial and store them in an array `invFact`. This can be done efficiently:
    a. Calculate `invFact[n]` as `modInverse(fact[n])` using the `power` function once.
    b. Use the relation `(k!)⁻¹ = ((k+1)!)⁻¹ * (k+1)` to compute the rest of the inverse factorials by iterating downwards: `invFact[i] = (invFact[i+1] * (i+1)) % MOD`.
4. Split the input string `s` into words.
5. Initialize `totalAnagrams` to 1.
6. Iterate through each `word`:
    a. Get length `n` and count character frequencies `c`.
    b. Start with `permutations = fact[n]`.
    c. For each character count `c > 1`, multiply by the pre-computed inverse factorial: `permutations = (permutations * invFact[c]) % MOD`.
    d. Update the total count: `totalAnagrams = (totalAnagrams * permutations) % MOD`.
7. Return `totalAnagrams`.

# Solutions
### Java

```java
import java.math.BigInteger ; class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int countAnagrams ( String s ) { int n = s . length (); long [] f = new long [ n + 1 ]; f [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; } long p = 1 ; for ( String w : s . split ( " " )) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < w . length (); ++ i ) { ++ cnt [ w . charAt ( i ) - 'a' ]; } p = p * f [ w . length ()] % MOD ; for ( int v : cnt ) { p = p * BigInteger . valueOf ( f [ v ]). modInverse ( BigInteger . valueOf ( MOD )). intValue () % MOD ; } } return ( int ) p ; } }
```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int countAnagrams(string s) {
    stringstream ss(s);
    string w;
    long ans = 1, mul = 1;
    while (ss >> w) {
      int cnt[26] = {0};
      for (int i = 1; i <= w.size(); ++i) {
        int c = w[i - 1] - 'a';
        ++cnt[c];
        ans = ans * i % mod;
        mul = mul * cnt[c] % mod;
      }
    }
    return ans * pow(mul, mod - 2) % mod;
  }
  long pow(long x, int n) {
    long res = 1L;
    for (; n; n /= 2) {
      if (n % 2)
        res = res * x % mod;
      x = x * x % mod;
    }
    return res;
  }
};

```

### Python

```python
mod = 10 ** 9 + 7 f = [ 1 ] for i in range ( 1 , 10 ** 5 + 1 ): f . append ( f [ - 1 ] * i % mod ) class Solution : def countAnagrams ( self , s : str ) -> int : ans = 1 for w in s . split (): cnt = Counter ( w ) ans *= f [ len ( w )] ans %= mod for v in cnt . values (): ans *= pow ( f [ v ], - 1 , mod ) ans %= mod return ans
```