Count Anagrams solution and explanation
7 more videos on this problem
Leetcode Biweekly Contest 94 | 2514 : Count Anagrams Solution | Explanation + Code | Newton SchoolCoding Community | Newton School · 15:58 · 1K views
Count Anagrams | 2514 LeetCode | Strings | Number of Ways | Anagrams | Leetcode Biweekly Contest 94CodeWithSunny · 11:49 · 1K views
Leetcode BiWeekly contest 94 - Hard - Count AnagramsPrakhar Agrawal · 13:53 · 1K views
2514. Count Anagrams (Leetcode Hard)Programming Live with Larry · 14:09 · 983 views
Count Anagrams (ALL THE PROOFs involved) | Biweekly Contest 94codingMohan · 34:49 · 860 views
LeetCode 2514. Count Anagrams | Simple Explanation with CodeDeep Tech · 15:06 · 778 views
【每日一题】LeetCode 2514. Count AnagramsHuifeng Guan · 15:44 · 485 views
Leetcode Biweekly Contest 94 | problem d | 2514. Count Anagrams | 24/12/22CodingVerse · 10:14 · 55 views
The 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 of distinct anagrams of s. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
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:
Input: s = "aa" Output: 1 Explanation: There is only one anagram possible for the given string.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters and spaces' '.- There is single space between consecutive words.
Approach overview
Problem Overview: You receive a sentence containing multiple words separated by spaces. For each word, count how many distinct anagrams can be formed using its characters, then multiply the counts across all words. Because characters may repeat, the number of valid permutations must account for duplicate letters and the result is returned modulo 1e9+7.
Approach 1: Factorial Counting with Frequency Map (O(n) time, O(n) space)
This approach treats each word independently and uses classic combinatorics for permutations with duplicates. For a word of length k, the number of unique permutations is k! / (freq[c1]! * freq[c2]! ...), where freq is the count of each character. You compute character frequencies using a hash table, then evaluate the formula using precomputed factorials and modular inverses under modulo 1e9+7. Precomputing factorials up to the total string length allows constant-time factorial lookups. Multiply the result for each word to obtain the final answer. Time complexity is O(n) where n is the sentence length, and space complexity is O(n) for factorial tables.
The key insight: repeated characters reduce the total permutations. Using modular inverse avoids division under modulo arithmetic. This is a direct application of combinatorics and modular math, and it scales easily for long strings because factorial values are reused.
Approach 2: Dynamic Programming on Permutation Construction (O(k * alphabet) per word, O(k) space)
This method builds permutations incrementally. For each word, you track how many characters of each type have been placed and compute the number of ways to build permutations step by step. A DP state represents how many characters have been used so far, and transitions add another character while respecting its frequency limit. The transition count reflects how many positions the new character can occupy relative to previously placed characters. This technique avoids direct factorial formulas and instead derives counts through iterative state updates.
Although conceptually useful for understanding permutation counting, the DP approach is slower and more complex to implement. Each word requires iterating through its characters and updating states based on remaining frequencies. Time complexity depends on word length and alphabet size, typically around O(k * 26) per word with O(k) space.
Recommended for interviews: The factorial counting approach is the expected solution. It demonstrates knowledge of permutation formulas, modular arithmetic, and efficient preprocessing. Interviewers want to see you recognize the formula for permutations with duplicates and implement factorial + modular inverse correctly. The DP approach is rarely required but shows deeper understanding of permutation construction.
Approach 1: Factorial Counting Approach
This approach uses the factorial formula to count permutations of each word while considering repeated characters. For a word with characters having counts n1, n2,..., the number of permutations is factorial(length) / (factorial(n1) * factorial(n2) * ...). We compute this for each word in the string.
from collections import Counter
from math import factorial
MOD = 10**9 + 7
def count_anagrams(s):
words = s.split()
result = 1
for word in words:
count = Counter(word)
word_length = len(word)
perm_count = factorial(word_length)
for freq in count.values():
perm_count //= factorial(freq)
result *= perm_count
result %= MOD
return result
# Example usage:
s = "too hot"
print(count_anagrams(s)) # Output: 18import java.util.HashMap;
import java.util.Map;
public class AnagramCounter {
private static final int MOD = 1000000007;
public static long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result = (result * i) % MOD;
}
return result;
}
public static int countAnagrams(String s) {
String[] words = s.split(" ");
long result = 1;
for (String word : words) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : word.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
long perm_count = factorial(word.length());
for (int count : freq.values()) {
perm_count = perm_count * modularInverse(factorial(count), MOD) % MOD;
}
result = (result * perm_count) % MOD;
}
return (int) result;
}
private static long modularInverse(long a, int mod) {
long m0 = mod, t, q;
long x0 = 0, x1 = 1;
if (mod == 1)
return 0;
while (a > 1) {
q = a / mod;
t = mod;
mod = (int) (a % mod);
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0)
x1 += m0;
return x1;
}
public static void main(String[] args) {
String s = "too hot";
System.out.println(countAnagrams(s)); // Output: 18
}
}#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>
using namespace std;
const int MOD = 1000000007;
long long factorial(int n) {
long long result = 1;
for (int i = 2; i <= n; ++i) {
result = (result * i) % MOD;
}
return result;
}
int countAnagrams(string s) {
stringstream ss(s);
string word;
long long result = 1;
while (ss >> word) {
unordered_map<char, int> freq;
for (char c : word) {
freq[c]++;
}
long long perm_count = factorial(word.size());
for (auto& [char_, count_] : freq) {
perm_count = perm_count * modularInverse(factorial(count_), MOD) % MOD;
}
result = result * perm_count % MOD;
}
return result;
}
long long modularInverse(long long n, int mod) {
// Fermat's little theorem
long long result = 1, exponent = mod-2;
while (exponent) {
if (exponent % 2) result = (result * n) % mod;
n = (n * n) % mod;
exponent /= 2;
}
return result;
}
int main() {
string s = "too hot";
cout << countAnagrams(s) << endl; // Output: 18
return 0;
}const MOD = 1000000007;
function factorial(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result = (result * i) % MOD;
}
return result;
}
function modularInverse(a, mod) {
let m0 = mod, x0 = 0, x1 = 1;
if (mod === 1) return 0;
while (a > 1) {
let q = Math.floor(a / mod);
let t = mod;
mod = a % mod;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
function countAnagrams(s) {
const words = s.split(' ');
let result = 1;
for (const word of words) {
const freq = {};
for (const c of word) {
freq[c] = (freq[c] || 0) + 1;
}
let permCount = factorial(word.length);
for (const count of Object.values(freq)) {
permCount = permCount * modularInverse(factorial(count), MOD) % MOD;
}
result = (result * permCount) % MOD;
}
return result;
}
// Example usage:
const s = "too hot";
console.log(countAnagrams(s)); // Output: 18using System;
using System.Collections.Generic;
public class Solution {
private const int MOD = 1000000007;
public static long Factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result = (result * i) % MOD;
}
return result;
}
public static int CountAnagrams(string s) {
var words = s.Split(' ');
long result = 1;
foreach (var word in words) {
var freq = new Dictionary<char, int>();
foreach (var c in word) {
if (!freq.ContainsKey(c)) freq[c] = 0;
freq[c]++;
}
long permCount = Factorial(word.Length);
foreach (var count in freq.Values) {
permCount = permCount * ModularInverse(Factorial(count), MOD) % MOD;
}
result = result * permCount % MOD;
}
return (int)result;
}
private static long ModularInverse(long a, int mod) {
long m0 = mod, x0 = 0, x1 = 1;
if (mod == 1) return 0;
while (a > 1) {
long q = a / mod;
long t = mod;
mod = a % mod;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
public static void Main(string[] args) {
string s = "too hot";
Console.WriteLine(CountAnagrams(s)); // Output: 18
}
}This Python solution splits the sentence into words and uses the collections.Counter to count the frequency of characters in each word. Using the factorial function, it calculates permutations by dividing the factorial of the word's length by the factorial of the frequencies, thereby accounting for character repetitions.
Time Complexity: O(n * m), where n is the number of words and m is the maximum length of a word due to frequency counting and factorial calculations. Space Complexity: O(m) for storing frequency counts for the longest word.
Approach 2: Dynamic Programming Approach on Permutations
In this approach, a more complex method involves using dynamic programming to reduce redundant calculations when determining permutation possibilities. The computation progressively builds on solutions to sub-problems of smaller segments of the input string, effectively using previous results to minimize computation.
from collections import Counter
MOD = 10**9 + 7
# Precompute factorials to save time later
max_factorial = 1000000
factorials = [1] * (max_factorial + 1)
for i in range(2, max_factorial + 1):
factorials[i] = (factorials[i - 1] * i) % MOD
# Precompute factorial inverses
factorial_inverses = [1] * (max_factorial + 1)
for i in range(2, max_factorial + 1):
factorial_inverses[i] = pow(factorials[i], MOD - 2, MOD)
def count_permutations(word):
count = Counter(word)
total_perms = factorials[len(word)]
for freq in count.values():
total_perms *= factorial_inverses[freq]
total_perms %= MOD
return total_perms
def count_anagrams_dp(s):
words = s.split()
result = 1
for word in words:
result *= count_permutations(word)
result %= MOD
return result
# Example usage:
s = "too hot"
print(count_anagrams_dp(s)) # Output: 18#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>
using namespace std;
const int MOD = 1000000007;
const int max_factorial = 1000000;
vector<long long> factorials(max_factorial + 1, 1);
vector<long long> inverses(max_factorial + 1, 1);
void precompute() {
for (int i = 2; i <= max_factorial; ++i) {
factorials[i] = (factorials[i - 1] * i) % MOD;
}
for (int i = 2; i <= max_factorial; ++i) {
inverses[i] = modularInverse(factorials[i]);
}
}
long long modularInverse(long long a) {
long long m = MOD, x0 = 0, x1 = 1;
while (a > 1) {
long long q = a / m;
long long t = m;
m = a % m;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += MOD;
return x1;
}
long long countPermutations(const string& word) {
unordered_map<char, int> freq;
for (char c : word) {
freq[c]++;
}
long long total_perms = factorials[word.size()];
for (auto& pair : freq) {
total_perms = (total_perms * inverses[pair.second]) % MOD;
}
return total_perms;
}
int countAnagramsDP(string s) {
precompute();
istringstream ss(s);
string word;
long long result = 1;
while (ss >> word) {
result = (result * countPermutations(word)) % MOD;
}
return result;
}
int main() {
string s = "too hot";
cout << countAnagramsDP(s) << endl; // Output: 18
return 0;
}This Python version employs precomputation of factorials and their inverses to avoid repeated calculations, efficiently counting permutations with dynamic programming principles by reducing repeated work across similar sub-problems.
Time Complexity for precomputation: O(n) and O(m) per word for permutation counting. Space Complexity: O(n) for precomputed factorials and inverses.
Approach 3: Default Approach
const mod int = 1e9 + 7
func countAnagrams(s string) int {
ans, mul := 1, 1
for _, w := range strings.Split(s, " ") {
cnt := [26]int{}
for i, c := range w {
i++
cnt[c-'a']++
ans = ans * i % mod
mul = mul * cnt[c-'a'] % mod
}
}
return ans * pow(mul, mod-2) % mod
}
func pow(x, n int) int {
res := 1
for ; n > 0; n >>= 1 {
if n&1 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}Complexity comparison
| Approach | Complexity |
|---|---|
| Factorial Counting Approach | Time Complexity: O(n * m), where n is the number of words and m is the maximum length of a word due to frequency counting and factorial calculations. Space Complexity: O(m) for storing frequency counts for the longest word. |
| Dynamic Programming Approach on Permutations | Time Complexity for precomputation: O(n) and O(m) per word for permutation counting. Space Complexity: O(n) for precomputed factorials and inverses. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Factorial Counting with Frequency Map | O(n) | O(n) | General case. Best when modular arithmetic and factorial precomputation are allowed. |
| Dynamic Programming on Permutations | O(k * alphabet) per word | O(k) | Useful for learning permutation construction or when avoiding factorial math. |
Frequently asked questions
Is Count Anagrams easy or hard?
Count Anagrams is labeled Hard on LeetCode because it requires knowledge of combinatorics, modular inverses, and careful handling of large factorial values. The implementation becomes straightforward once you recognize the permutation-with-duplicates formula.
Count Anagrams Python/Java solution
In Python or Java, the typical solution precomputes factorials up to the maximum string length and uses modular exponentiation to compute inverse factorials. For each word, count character frequencies, apply the permutation formula with duplicates, and multiply the results modulo 1e9+7.
How to solve Count Anagrams in O(n)?
Split the sentence into words and process each word independently. For a word with length k, compute permutations with duplicates using the formula k! / (freq[c1]! * freq[c2]! ...). Precompute factorials and inverse factorials so each computation is constant time. Multiply the results modulo 1e9+7 to get the final answer.
What is the best approach for Count Anagrams?
The best approach uses combinatorics with factorial counting. For each word of length k, compute k! divided by the factorial of each character frequency (to handle duplicates). Precompute factorials and modular inverses under modulo 1e9+7, then multiply results across all words. This achieves O(n) time for the entire sentence.
Is Count Anagrams asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies like Google, Amazon, and Meta because it combines combinatorics with efficient modular arithmetic. Interviewers often use it to test understanding of permutations with duplicate elements and the ability to implement factorial + modular inverse logic.
What data structure is used in Count Anagrams?
A hash table (or frequency array) is used to count occurrences of each character in a word. These counts determine the denominator of the permutation formula. The solution also relies on arrays for factorial and inverse factorial precomputation.
What is the time complexity of Count Anagrams?
The optimal factorial-based solution runs in O(n) time where n is the total length of the sentence. Factorials and modular inverses are precomputed once, and each word only requires counting character frequencies and constant-time factorial lookups. Space complexity is O(n) for the factorial arrays.