Count Anagrams

Hard
1036.

Count Anagrams

Count Anagrams is a hard coding problem on strings, hash table and math, asked in Amazon, Google, Uber and MathWorks interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countAnagrams = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Anagrams — Solution in Python, Java & C++

Count Anagrams solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Count Anagrams is a hard coding problem on strings, hash table and math, asked in Amazon, Google, Uber and MathWorks interviews.

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.

Hints for Count Anagrams

  1. Hint 1

    The words are independent, so multiply their counts together.

  2. Hint 2

    A word of length L whose letters occur c₁, c₂, … times has L! / (c₁! · c₂! · …) distinct arrangements.

  3. Hint 3

    Division under a modulus means multiplying by a modular inverse — precompute factorials and inverse factorials once.

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

Java

public static int countAnagrams(String s) {
    final long MOD = 1000000007L;
    int n = s.length();
    long[] fact = new long[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    long[] invFact = new long[n + 1];
    long base = fact[n], e = MOD - 2, cur = 1;
    while (e > 0) {
        if ((e & 1L) == 1L) cur = cur * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    invFact[n] = cur;
    for (int i = n; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD;
    long answer = 1;
    for (String word : s.split(" ")) {
        int[] cnt = new int[26];
        for (int i = 0; i < word.length(); i++) cnt[word.charAt(i) - 'a']++;
        long ways = fact[word.length()];
        for (int c : cnt) {
            if (c > 1) ways = ways * invFact[c] % MOD;
        }
        answer = answer * ways % MOD;
    }
    return (int) answer;
}

C++

int countAnagrams(string s) {
    const long long MOD = 1000000007LL;
    int n = (int) s.size();
    vector<long long> fact(n + 1, 1), invFact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    long long base = fact[n], e = MOD - 2, cur = 1;
    while (e > 0) {
        if (e & 1LL) cur = cur * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    invFact[n] = cur;
    for (int i = n; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD;
    long long answer = 1;
    string word;
    vector<string> words;
    for (char c : s) {
        if (c == ' ') {
            words.push_back(word);
            word.clear();
        } else {
            word += c;
        }
    }
    words.push_back(word);
    for (auto& w : words) {
        vector<int> cnt(26, 0);
        for (char c : w) cnt[c - 'a']++;
        long long ways = fact[w.size()];
        for (int c : cnt) {
            if (c > 1) ways = ways * invFact[c] % MOD;
        }
        answer = answer * ways % MOD;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets