Count Anagrams

Multinomial coefficient with modular inverse

Multinomial coefficients. Precompute factorial + modular inverse.

Published Apr 16, 2026

Problem

Given a string s of lowercase letters separated by single spaces, return the number of distinct strings that are anagrams of s, modulo 10^9 + 7.

An anagram of s must have the same words (same positions), but each word can be independently rearranged. The total count is the product of the distinct permutations of each word.

Input

s = "too hot"

Output

Explanation

'too' has 3!/2! = 3 anagrams. 'hot' has 3!/1! = 6. Product = 18.

Input

s = "aa"

Output

Explanation

'aa' has only one arrangement.

Intuition

For a single word of length L with character frequencies c_1, c_2, ..., c_26, the number of distinct permutations is the multinomial coefficient: L! / (c_1! * c_2! * ... * c_26!).

Since MOD = 10^9 + 7 is prime, division becomes multiplication by the modular inverse: a / b mod p = a * b^(p-2) mod p (Fermat's little theorem).

The total answer is the product of multinomial coefficients across all words.

Approach

Brute Permutation

TimeO(Σ L_i!)

SpaceO(L)

Generate all permutations of each word, deduplicate, count. Only feasible for very short words.

impl Solution {
    pub fn count_anagrams(s: String) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut total: i64 = 1;
        for word in s.split(' ') {
            let mut chars: Vec<u8> = word.bytes().collect();
            chars.sort();
            let mut count: i64 = 1;
            loop {
                // next_permutation
                let n = chars.len();
                let mut i = n.wrapping_sub(2);
                while i < n && chars[i] >= chars[i + 1] {
                    if i == 0 { break; }
                    i = i.wrapping_sub(1);
                }
                if i >= n || (i == 0 && chars[0] >= chars[1]) { break; }
                let mut j = n - 1;
                while chars[j] <= chars[i] { j -= 1; }
                chars.swap(i, j);
                chars[i + 1..].reverse();
                count = 1;
            }
            total= total * count % MOD;
        }
        total as i32
    }
}

Rust · runnable

function countAnagrams(s: string): number {
  const MOD = 1_000_000_007n;
  let total = 1n;
  for (const word of s.split(' ')) {
    const chars = [...word].sort();
    let count = 1n;
    while (nextPerm(chars)) count++;
    total = total * count % MOD;
  }
  return Number(total);

  function nextPerm(a: string[]): boolean {
    let i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i < 0) return false;
    let j = a.length - 1;
    while (a[j] <= a[i]) j--;
    [a[i], a[j]] = [a[j], a[i]];
    let l = i + 1, r = a.length - 1;
    while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
    return true;
  }
}

TypeScript · runnable

Multinomial with Modular Inverse

TimeO(L)

SpaceO(L)

Recommended

Precompute factorials and inverse factorials up to L (total string length). For each word, multiply the running product by len! and divide by each freq!.

impl Solution {
    pub fn count_anagrams(s: String) -> i32 {
        const MOD: i64 = 1_000_000_007;

        fn mod_pow(mut base: i64, mut exp: i64, m: i64) -> i64 {
            let mut result = 1i64;
            base %= m;
            while exp > 0 {
                if exp & 1 == 1 {
                    result = result * base % m;
                }
                exp >>= 1;
                base = base * base % m;
            }
            result
        }

        let n = s.len();
        let mut fact = vec![1i64; n + 1];
        for i in 1..=n {
            fact[i] = fact[i - 1] * i as i64 % MOD;
        }
        let mut inv_fact = vec![1i64; n + 1];
        inv_fact[n] = mod_pow(fact[n], MOD - 2, MOD);
        for i in (0..n).rev() {
            inv_fact[i] = inv_fact[i + 1] * (i + 1) as i64 % MOD;
        }

        let mut ans: i64 = 1;
        for word in s.split(' ') {
            let mut freq = [0usize; 26];
            for b in word.bytes() {
                freq[(b - b'a') as usize] += 1;
            }
            ans = ans * fact[word.len()] % MOD;
            for &f in &freq {
                ans = ans * inv_fact[f] % MOD;
            }
        }

        ans as i32
    }
}

Rust · runnable

function countAnagrams(s: string): number {
  const MOD = 1_000_000_007n;

  const modPow = (base: bigint, exp: bigint, m: bigint): bigint => {
    let result = 1n;
    base %= m;
    while (exp > 0n) {
      if (exp & 1n) result = result * base % m;
      exp >>= 1n;
      base = base * base % m;
    }
    return result;
  };

  const n = s.length;
  const fact = new Array<bigint>(n + 1);
  fact[0] = 1n;
  for (let i = 1; i <= n; i++) fact[i]= fact[i - 1] * BigInt(i) % MOD;
  const invFact= new Array<bigint>(n + 1);
  invFact[n] = modPow(fact[n], MOD - 2n, MOD);
  for (let i = n - 1; i >= 0; i--) {
    invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;
  }

  let ans = 1n;
  for (const word of s.split(' ')) {
    const freq = new Array(26).fill(0);
    for (let i = 0; i < word.length; i++) {
      freq[word.charCodeAt(i) - 97]++;
    }
    ans= ans * fact[word.length] % MOD;
    for (const f of freq) {
      ans= ans * invFact[f] % MOD;
    }
  }

  return Number(ans);
}

TypeScript · runnable

Trace

s = "too hot". Total length L = 7 (including space is irrelevant; we process per word).

word	len	freq	multinomial	running product
too	3	t:1, o:2	3!/(1!·2!) = 3	3
hot	3	h:1, o:1, t:1	3!/(1!·1!·1!) = 6	18

Edge cases

Single character word — 1!/1! = 1. No contribution.
All same letters — n!/n! = 1.
All distinct letters — n!/1^n = n!.
Very long string — total length up to 10^5; precomputed factorials handle it in O(L).

Takeaway

The multinomial coefficient is the go-to formula for "distinct arrangements of items with repeats." The modular-inverse technique (a^(p-2) mod p via Fermat) is a fundamental toolkit item for competitive and production math — it shows up in probability, combinatorics, and cryptographic primitives alike.

Medium#62

Unique Paths

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Grid DP starting point.

Hard#1569

Ways to Reorder Array to Get Same BST

Recursive decomposition + nCr. Beautiful problem for your background.

Hard#1866

Rearrange Sticks With K Visible

Stirling numbers of the first kind. Pure combinatorial DP.