Skip to main content
Talentd

Count Anagrams - Solution & Explanation

HardHash TableMathStringCombinatorics13 min readAsked at: Mathworks
Practice this problem

Problem Statement

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 <= 105
  • s consists 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.

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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity for precomputation: O(n) and O(m) per word for permutation counting. Space Complexity: O(n) for precomputed factorials and inverses.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Factorial Counting with Frequency MapO(n)O(n)General case. Best when modular arithmetic and factorial precomputation are allowed.
Dynamic Programming on PermutationsO(k * alphabet) per wordO(k)Useful for learning permutation construction or when avoiding factorial math.

Video Solution

Leetcode Biweekly Contest 94 | 2514 : Count Anagrams Solution | Explanation + Code | Newton School • Coding Community | Newton School • 1,507 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Count Anagrams with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Ways to Build Rooms in an Ant Colony

Next

Group Anagrams