Get started

Count Anagrams — Hard Problem & Solution

s is a list of words separated by single spaces. Another string t is an anagram of s if it has the same number of words and, for every position, its i-th…

Problem statement

s is a list of words separated by single spaces. Another string t is an anagram of s if it has the same number of words and, for every position, its i-th word is a permutation of s's i-th word.

Return the number of distinct anagrams of s, modulo 10⁹ + 7. s itself counts as one of them.

Example 1

Input: s = "code kairo"
Output: 2880
Explanation: `code` has 4! = 24 arrangements and `kairo` has 5! = 120; 24 × 120 = 2880.

Example 2

Input: s = "too hot"
Output: 18
Explanation: `too` has only 3 distinct arrangements because the two `o`s are interchangeable; `hot` has 6.

Example 3

Input: s = "aa"
Output: 1
Explanation: Both letters are the same, so there is one arrangement.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters and spaces ' '.
  • There is single space between consecutive words.

How to solve Count Anagrams

Each word contributes its multinomial coefficient L! / ∏ cᵢ!, and the words are independent so the answers multiply. Precompute factorials and inverse factorials up to |s| once, then each word is a linear scan plus at most 26 multiplications.

Approach

  1. Build fact[0..n] with fact[i] = fact[i-1] · i mod p.
  2. Compute invFact[n] once with Fermat's little theorem — fact[n]^(p-2) — then walk down with invFact[i-1] = invFact[i] · i.
  3. Split s on spaces. For each word, tally its letters and multiply fact[L] by invFact[cᵢ] for every letter.
  4. Multiply the per-word results together, modulo 10⁹ + 7.

Why it works

Two things make this efficient. First, deriving the whole inverse-factorial table from a single modular exponentiation — the identity invFact[i-1] = invFact[i] · i — turns O(n log p) into O(n + log p). Second, repeated letters are why the answer is not simply L!: swapping two identical letters produces the same string, so each group of cᵢ identical letters over-counts by exactly cᵢ!.

Complexity

  • Time — O(n + log p)
  • Space — O(n)

Pitfalls

  • Dividing by ∏ cᵢ! modulo a prime requires a modular inverse; integer division is wrong.
  • In a language with 64-bit integers, a * b for residues near 10⁹ overflows a double — use the split trick or 64-bit arithmetic.
  • The factorial table must reach the length of the longest word, which can be all of s.

Reference solution

Python

def countAnagrams(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD
    answer = 1
    for word in s.split(" "):
        cnt = [0] * 26
        for c in word:
            cnt[ord(c) - 97] += 1
        ways = fact[len(word)]
        for c in cnt:
            if c > 1:
                ways = ways * inv_fact[c] % MOD
        answer = answer * ways % MOD
    return answer

JavaScript

var countAnagrams = function(s) {
    var MOD = 1000000007;
    var mulmod = function(a, b) {
        var ah = Math.floor(a / 65536), al = a % 65536;
        return ((ah * b % MOD) * 65536 + al * b) % MOD;
    };
    var powmod = function(base, exp) {
        var result = 1, bb = base % MOD, e = exp;
        while (e > 0) {
            if (e % 2 === 1) result = mulmod(result, bb);
            bb = mulmod(bb, bb);
            e = Math.floor(e / 2);
        }
        return result;
    };
    var n = s.length, i;
    var fact = [1];
    for (i = 1; i <= n; i++) fact.push(mulmod(fact[i - 1], i));
    var invFact = [];
    for (i = 0; i <= n; i++) invFact.push(1);
    invFact[n] = powmod(fact[n], MOD - 2);
    for (i = n; i >= 1; i--) invFact[i - 1] = mulmod(invFact[i], i);
    var answer = 1;
    var words = s.split(" ");
    for (var w = 0; w < words.length; w++) {
        var word = words[w];
        var cnt = [];
        for (i = 0; i < 26; i++) cnt.push(0);
        for (i = 0; i < word.length; i++) cnt[word.charCodeAt(i) - 97]++;
        var ways = fact[word.length];
        for (i = 0; i < 26; i++) {
            if (cnt[i] > 1) ways = mulmod(ways, invFact[cnt[i]]);
        }
        answer = mulmod(answer, ways);
    }
    return answer;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue