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.

Description Hints 3 Solution Video 15:58

2514. Count Anagrams

Hard38.4% acceptance1 company

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 i^th word of t is a permutation of the i^th 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 10⁹ + 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 <= 10⁵
s consists of lowercase English letters and spaces ' '.
There is single space between consecutive words.

Asked at 1 company

Mathworks

Topics

Hints open one at a time

Hint 1

For each word, can you count the number of permutations possible if all characters are distinct?

Hint 2

How to reduce overcounting when letters are repeated?

Hint 3

The product of the counts of distinct permutations of all words will give the final answer.

15:58

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution