Problem 39.9 · Math for Coding InterviewsHard

Count Anagrams

PatternNumber Theory and Combinatorics Frequency Counting

What it teaches: Multinomial coefficients under a modulus with factorials and inverse factorials.

Practise it on judges as “Count Anagrams”.

In plain words

Each word can be scrambled on its own, and the words stay in their places, so multiply the number of scrambles of each word. A word with L letters has L! orderings, but swapping two identical letters gives the same word, so divide by (count)! for each repeated letter. Division under a modulus is done by multiplying with an "inverse".

Return the count modulo 10⁹ + 7. Example: s = "too hot" → 18.

The problem

s is words separated by single spaces. Count the distinct strings formed by rearranging the letters within each word (words stay in place), modulo 10⁹ + 7.

Example 1

Input: s = "too hot"
Output: 18

"too": 3 arrangements, "hot": 6.

Constraints

1 ≤ s.length ≤ 10⁵

Pattern clues in the wording

→ Arrangements with repeated letters
→ Modulo 10⁹ + 7

These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int countAnagrams(String s) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	s = "too hot"	18
2	s = "aa"	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Multinomials with inverse factorials · O(n + log p)

Multinomials with inverse factorials

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

fact and invFact up to the longest word. For each word multiply by fact[L] and invFact[count] for each letter.

▶ Dry run: Multiply L! / (repeats)! per words = "too hot"

counts(map)

t: 1o: 2

result(vars)

1 × 3! = 66 ÷ 1! ÷ 2! = 3

Step 1/3"too": 3 letters give 3! = 6 orders, but the two o's can swap without change, so divide by 2: 3 (too, oto, oot).

Approach 1

class Solution {
    private static final long P = 1_000_000_007L;

    public int countAnagrams(String s) {
        int n = s.length();
        long[] fact = new long[n + 1], inv = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % P;
        inv[n] = power(fact[n], P - 2);
        for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % P;
        long result = 1;
        for (String w : s.split(" ")) {
            int[] count = new int[26];
            for (char c : w.toCharArray()) count[c - 'a']++;
            result = result * fact[w.length()] % P;
            for (int c : count) result = result * inv[c] % P;
        }
        return (int) result;
    }

    private long power(long b, long e) {
        long r = 1;
        b %= P;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % P;
            b = b * b % P;
            e >>= 1;
        }
        return r;
    }
}

Verdict: Each word costs O(L + 26).

Before you submit

Edge cases and common mistakes

Test these inputs

Words of one repeated letter (1)
One long word

Mistakes people make

Dividing factorials directly under the modulus.

Interview

Follow-up questions

Why compute inverse factorials backwards?

Command Palette

The problem

Approaches

Multinomials with inverse factorials

Edge cases and common mistakes

Follow-up questions