Count Anagrams

Problem

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 ofdistinct anagrams of _s. Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3


Input: s = "too hot"
Output: 18
Explanation: Some of the anagrams of the given string are "too hot", "oot hot", "oto toh", "too toh", and "too oht".

Example 2

1
2
3


Input: s = "aa"
Output: 1
Explanation: There is only one anagram possible for the given string.

Constraints

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

Solution

Method 1 – Combinatorics with Modular Inverse 1

Intuition

Each word in the string can be rearranged independently. The number of anagrams for a word is the multinomial coefficient: total letters factorial divided by the product of factorials of each letter’s frequency. The answer is the product of anagram counts for all words, modulo 10^9+7.

Approach

Split the string into words by spaces.
For each word:
- Count the frequency of each character.
- Compute the total number of anagrams as total_letters! / (freq1! * freq2! * …).
- Use modular arithmetic and precomputed factorials/inverses for efficiency.
Multiply the results for all words, taking modulo 10^9+7.
Return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


class Solution {
public:
    int countAnagrams(string s) {
        const int MOD = 1e9+7, N = 100005;
        vector<long long> fact(N), inv(N);
        fact[0] = 1;
        for (int i = 1; i < N; ++i) fact[i] = fact[i-1] * i % MOD;
        inv[N-1] = powmod(fact[N-1], MOD-2, MOD);
        for (int i = N-2; i >= 0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
        auto split = [](string& s) {
            vector<string> res;
            string t;
            for (char c : s) {
                if (c == ' ') {
                    if (!t.empty()) res.push_back(t);
                    t.clear();
                } else t += c;
            }
            if (!t.empty()) res.push_back(t);
            return res;
        };
        auto words = split(s);
        long long ans = 1;
        for (auto& w : words) {
            vector<int> cnt(26);
            for (char c : w) cnt[c-'a']++;
            long long cur = fact[w.size()];
            for (int x : cnt) cur = cur * inv[x] % MOD;
            ans = ans * cur % MOD;
        }
        return ans;
    }
    long long powmod(long long a, long long b, long long m) {
        long long res = 1;
        while (b) {
            if (b & 1) res = res * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


func countAnagrams(s string) int {
    const MOD = 1_000_000_007
    N := 100005
    fact := make([]int, N)
    inv := make([]int, N)
    fact[0] = 1
    for i := 1; i < N; i++ {
        fact[i] = fact[i-1] * i % MOD
    }
    inv[N-1] = powmod(fact[N-1], MOD-2, MOD)
    for i := N-2; i >= 0; i-- {
        inv[i] = inv[i+1] * (i+1) % MOD
    }
    words := strings.Fields(s)
    ans := 1
    for _, w := range words {
        cnt := [26]int{}
        for _, c := range w {
            cnt[c-'a']++
        }
        cur := fact[len(w)]
        for _, x := range cnt {
            cur = cur * inv[x] % MOD
        }
        ans = ans * cur % MOD
    }
    return ans
}
func powmod(a, b, m int) int {
    res := 1
    for b > 0 {
        if b&1 == 1 {
            res = res * a % m
        }
        a = a * a % m
        b >>= 1
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
    public int countAnagrams(String s) {
        final int MOD = 1_000_000_007, N = 100005;
        long[] fact = new long[N], inv = new long[N];
        fact[0] = 1;
        for (int i = 1; i < N; ++i) fact[i] = fact[i-1] * i % MOD;
        inv[N-1] = powmod(fact[N-1], MOD-2, MOD);
        for (int i = N-2; i >= 0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
        String[] words = s.split(" ");
        long ans = 1;
        for (String w : words) {
            int[] cnt = new int[26];
            for (char c : w.toCharArray()) cnt[c-'a']++;
            long cur = fact[w.length()];
            for (int x : cnt) cur = cur * inv[x] % MOD;
            ans = ans * cur % MOD;
        }
        return (int)ans;
    }
    long powmod(long a, long b, long m) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
    fun countAnagrams(s: String): Int {
        val MOD = 1_000_000_007
        val N = 100005
        val fact = LongArray(N)
        val inv = LongArray(N)
        fact[0] = 1L
        for (i in 1 until N) fact[i] = fact[i-1] * i % MOD
        inv[N-1] = powmod(fact[N-1], (MOD-2).toLong(), MOD.toLong())
        for (i in N-2 downTo 0) inv[i] = inv[i+1] * (i+1) % MOD
        val words = s.split(" ")
        var ans = 1L
        for (w in words) {
            val cnt = IntArray(26)
            for (c in w) cnt[c-'a']++
            var cur = fact[w.length]
            for (x in cnt) cur = cur * inv[x] % MOD
            ans = ans * cur % MOD
        }
        return ans.toInt()
    }
    fun powmod(a: Long, b: Long, m: Long): Long {
        var a = a; var b = b; var res = 1L
        while (b > 0) {
            if (b and 1L == 1L) res = res * a % m
            a = a * a % m
            b = b shr 1
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def countAnagrams(self, s: str) -> int:
        MOD = 10**9 + 7
        N = 100005
        fact = [1] * N
        inv = [1] * N
        for i in range(1, N):
            fact[i] = fact[i-1] * i % MOD
        inv[N-1] = pow(fact[N-1], MOD-2, MOD)
        for i in range(N-2, -1, -1):
            inv[i] = inv[i+1] * (i+1) % MOD
        ans = 1
        for w in s.split():
            cnt = [0] * 26
            for c in w:
                cnt[ord(c)-ord('a')] += 1
            cur = fact[len(w)]
            for x in cnt:
                cur = cur * inv[x] % MOD
            ans = ans * cur % MOD
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


impl Solution {
    pub fn count_anagrams(s: String) -> i32 {
        const MOD: i64 = 1_000_000_007;
        const N: usize = 100005;
        let mut fact = vec![1i64; N];
        let mut inv = vec![1i64; N];
        for i in 1..N {
            fact[i] = fact[i-1] * i as i64 % MOD;
        }
        inv[N-1] = powmod(fact[N-1], MOD-2, MOD);
        for i in (0..N-1).rev() {
            inv[i] = inv[i+1] * (i as i64 + 1) % MOD;
        }
        let words: Vec<&str> = s.split_whitespace().collect();
        let mut ans = 1i64;
        for w in words {
            let mut cnt = [0; 26];
            for c in w.chars() {
                cnt[(c as u8 - b'a') as usize] += 1;
            }
            let mut cur = fact[w.len()];
            for &x in &cnt {
                cur = cur * inv[x] % MOD;
            }
            ans = ans * cur % MOD;
        }
        ans as i32
    }
}
fn powmod(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut res = 1;
    while b > 0 {
        if b & 1 == 1 {
            res = res * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    countAnagrams(s: string): number {
        const MOD = 1_000_000_007, N = 100005;
        const fact: number[] = Array(N).fill(1), inv: number[] = Array(N).fill(1);
        for (let i = 1; i < N; ++i) fact[i] = fact[i-1] * i % MOD;
        inv[N-1] = powmod(fact[N-1], MOD-2, MOD);
        for (let i = N-2; i >= 0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
        let ans = 1;
        for (const w of s.split(' ')) {
            const cnt = Array(26).fill(0);
            for (const c of w) cnt[c.charCodeAt(0)-97]++;
            let cur = fact[w.length];
            for (const x of cnt) cur = cur * inv[x] % MOD;
            ans = ans * cur % MOD;
        }
        return ans;
    }
}
function powmod(a: number, b: number, m: number): number {
    let res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Complexity

⏰ Time complexity: O(L + W * D), where L is the length of s, W is the number of words, and D is the max word length. Precomputation is O(N), and each word is processed in O(D).
🧺 Space complexity: O(N), for factorials and inverses.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Combinatorics with Modular Inverse 1#

Intuition#

Approach#

Code#

Complexity#