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.
"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 <= 105s consists of lowercase English letters and spaces ' '.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.
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.
Python
C++
Java
JavaScript
C#
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.
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.
Time Complexity for precomputation: O(n) and O(m) per word for permutation counting. Space Complexity: O(n) for precomputed factorials and inverses.
| 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 | — |
| 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. |
Leetcode Biweekly Contest 94 | 2514 : Count Anagrams Solution | Explanation + Code | Newton School • Coding Community | Newton School • 1,396 views views
Watch 7 more video solutions →Practice Count Anagrams with our built-in code editor and test cases.
Practice on FleetCode