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.
- Difficulty: Hard
- Topics: Strings, Hash Table, Math, Counting, Combinatorics
- Asked at: Amazon, Google, Uber, MathWorks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^5s consists of lowercase English letters and spaces ' '.There is single space between consecutive words.
Hints for Count Anagrams
Hint 1
The words are independent, so multiply their counts together.
Hint 2
A word of length
Lwhose letters occurc₁, c₂, …times hasL! / (c₁! · c₂! · …)distinct arrangements.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
- Build
fact[0..n]withfact[i] = fact[i-1] · i mod p. - Compute
invFact[n]once with Fermat's little theorem —fact[n]^(p-2)— then walk down withinvFact[i-1] = invFact[i] · i. - Split
son spaces. For each word, tally its letters and multiplyfact[L]byinvFact[cᵢ]for every letter. - 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 * bfor 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 answerJava
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