Count anagrams

Hash Table Math String Combinatorics Counting

37.0% acceptance

Feb 25, 2026

473

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 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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

    fn pow_mod(mut base: u64, mut exp: u64, m: u64) -> u64 {
      let mut result = 1u64;
      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![1u64; n + 1];
    for i in 1..=n {
      fact[i] = fact[i - 1] * i as u64 % MOD;
    }

    let mut ans = 1u64;
    for word in s.split(' ') {
      let len = word.len();
      ans = ans * fact[len] % MOD;
      let mut freq = [0usize; 26];
      for b in word.bytes() {
        freq[(b - b'a') as usize] += 1;
      }
      for &f in &freq {
        if f > 1 {
          let inv = pow_mod(fact[f], MOD - 2, MOD);
          ans = ans * inv % MOD;
        }
      }
    }
    ans as i32
  }
}