Count Anagrams — DSA · Engineering Playbook

Problem#

A “good” string is any permutation of s (space-separated words) such that each word is replaced by an anagram of itself (spaces stay in place). Return the count of good strings modulo 10^9 + 7.

Examples#

s = "too hot" → 18 (3!/2! * 3! = 18).
s = "aa" → 1.

Constraints#

1 <= s.length <= 10^5.

Hints#

Hint

For each word, anagrams = L! / prod(count[c]!). Multiply across words.

Approach#

Precompute factorials and modular inverses up to N. For each word, multiply L! by the modular inverse of prod(count[c]!). Accumulate across all words.

Solution#

class Solution {
    static const int MOD = 1'000'000'007;
    long long power(long long a, long long b, long long mod) {
        long long r = 1; a %= mod;
        while (b) { if (b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; }
        return r;
    }
public:
    int countAnagrams(string s) {
        int n = s.size();
        vector<long long> fact(n + 1, 1);
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
        long long ans = 1;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s[j] != ' ') ++j;
            int L = j - i;
            int cnt[26] = {0};
            for (int k = i; k < j; ++k) ++cnt[s[k] - 'a'];
            long long word = fact[L];
            for (int c = 0; c < 26; ++c) if (cnt[c] > 1)
                word = word * power(fact[cnt[c]], MOD - 2, MOD) % MOD;
            ans = ans * word % MOD;
            i = j + 1;
        }
        return static_cast<int>(ans);
    }
};

func countAnagrams(s string) int {
    const MOD = 1_000_000_007
    power := func(a, b int64) int64 {
        r, base := int64(1), a%MOD
        for b > 0 {
            if b&1 == 1 {
                r = r * base % MOD
            }
            base = base * base % MOD
            b >>= 1
        }
        return r
    }
    n := len(s)
    fact := make([]int64, n+1)
    fact[0] = 1
    for i := 1; i <= n; i++ {
        fact[i] = fact[i-1] * int64(i) % MOD
    }
    ans := int64(1)
    i := 0
    for i < n {
        j := i
        for j < n && s[j] != ' ' {
            j++
        }
        L := j - i
        var cnt [26]int
        for k := i; k < j; k++ {
            cnt[s[k]-'a']++
        }
        word := fact[L]
        for c := 0; c < 26; c++ {
            if cnt[c] > 1 {
                word = word * power(fact[cnt[c]], MOD-2) % MOD
            }
        }
        ans = ans * word % MOD
        i = j + 1
    }
    return int(ans)
}

from math import factorial

class Solution:
    def countAnagrams(self, s: str) -> int:
        MOD = 1_000_000_007
        n = len(s)
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i % MOD
        ans = 1
        i = 0
        while i < n:
            j = i
            while j < n and s[j] != ' ':
                j += 1
            L = j - i
            cnt = [0] * 26
            for k in range(i, j):
                cnt[ord(s[k]) - ord('a')] += 1
            word = fact[L]
            for c in range(26):
                if cnt[c] > 1:
                    word = word * pow(fact[cnt[c]], MOD - 2, MOD) % MOD
            ans = ans * word % MOD
            i = j + 1
        return ans

function countAnagrams(s) {
    const MOD = 1_000_000_007n;
    const n = s.length;
    const power = (a, b) => {
        let r = 1n;
        a %= MOD;
        while (b > 0n) {
            if (b & 1n) r = (r * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1n;
        }
        return r;
    };
    const fact = new Array(n + 1).fill(1n);
    for (let i = 1; i <= n; i++) fact[i] = (fact[i - 1] * BigInt(i)) % MOD;
    let ans = 1n;
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && s[j] !== ' ') j++;
        const L = j - i;
        const cnt = new Array(26).fill(0);
        for (let k = i; k < j; k++) cnt[s.charCodeAt(k) - 97]++;
        let word = fact[L];
        for (let c = 0; c < 26; c++) {
            if (cnt[c] > 1) {
                word = (word * power(fact[cnt[c]], MOD - 2n)) % MOD;
            }
        }
        ans = (ans * word) % MOD;
        i = j + 1;
    }
    return Number(ans);
}

class Solution {
    private static final int MOD = 1_000_000_007;

    public int countAnagrams(String s) {
        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 ans = 1;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) != ' ') j++;
            int L = j - i;
            int[] cnt = new int[26];
            for (int k = i; k < j; k++) cnt[s.charAt(k) - 'a']++;
            long word = fact[L];
            for (int c = 0; c < 26; c++) {
                if (cnt[c] > 1) {
                    word = word * power(fact[cnt[c]], MOD - 2) % MOD;
                }
            }
            ans = ans * word % MOD;
            i = j + 1;
        }
        return (int) ans;
    }

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

function countAnagrams(s: string): number {
    const MOD = 1_000_000_007n;
    const n = s.length;
    const power = (a: bigint, b: bigint): bigint => {
        let r = 1n;
        a %= MOD;
        while (b > 0n) {
            if (b & 1n) r = (r * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1n;
        }
        return r;
    };
    const fact: bigint[] = new Array(n + 1).fill(1n);
    for (let i = 1; i <= n; i++) fact[i] = (fact[i - 1] * BigInt(i)) % MOD;
    let ans = 1n;
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && s[j] !== ' ') j++;
        const L = j - i;
        const cnt: number[] = new Array(26).fill(0);
        for (let k = i; k < j; k++) cnt[s.charCodeAt(k) - 97]++;
        let word = fact[L];
        for (let c = 0; c < 26; c++) {
            if (cnt[c] > 1) {
                word = (word * power(fact[cnt[c]], MOD - 2n)) % MOD;
            }
        }
        ans = (ans * word) % MOD;
        i = j + 1;
    }
    return Number(ans);
}

Editorial#

Each word’s anagram count is the multinomial L! / prod(cnt[c]!). Working under a prime modulus, division becomes multiplication by Fermat’s little theorem inverse. Words are independent, so total count multiplies across words. Precomputed factorials keep each word’s work O(L + 26 log MOD).

Complexity#

Time: O(N + 26 log MOD) total.
Space: O(N) for factorials.

Concept revision#

Group Anagrams