Count Anagrams
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the mathematical formula for permutations into code. For each word, it calculates the number of distinct permutations and multiplies this into a running total. The formula for permutations of a word of length n with character counts c1, c2, ... is n! / (c1! * c2! * ... * ck!).
To handle the modulo arithmetic, division is replaced by multiplication with the modular multiplicative inverse. Since 10^9 + 7 is a prime number, we can use Fermat's Little Theorem to find the inverse of a as a^(MOD-2) % MOD. This requires a helper function for modular exponentiation (also known as power function).
Helper functions for factorial, power, and modInverse are created and called as needed for each word.
Algorithm
- Define a constant
MOD = 10^9 + 7. - Implement a
power(base, exp)function for modular exponentiation to calculate(base^exp) % MODefficiently. - Implement a
modInverse(n)function that uses thepowerfunction to find the modular multiplicative inverse:power(n, MOD - 2). - Implement a
factorial(n)function that calculatesn!moduloMODby iterating from 2 ton. - Split the input string
sby spaces to get an array of words. - Initialize a variable
totalAnagramsto 1. - Iterate through each
wordin the array: a. Determine the length of the word,n. b. Count the frequency of each character in the word. c. Calculate the number of permutations for the current word using the formula:n! / (c1! * c2! * ...). d. The calculation in modulo arithmetic is:permutations = factorial(n). e. For each character countcgreater than 1, update the permutations:permutations = (permutations * modInverse(factorial(c))) % MOD. f. Multiply this result into thetotalAnagrams:totalAnagrams = (totalAnagrams * permutations) % MOD. - Return
totalAnagrams.
Walkthrough
The core of this method is to process each word independently. We first split the input string s into words. Then, for each word, we calculate how many unique ways its letters can be rearranged.
The number of permutations for a single word is given by the multinomial coefficient formula. For a word of length n, with k unique characters appearing c1, c2, ..., ck times respectively, the number of permutations is n! / (c1! * c2! * ... * ck!).
Since we need the result modulo 10^9 + 7, we perform all calculations within this finite field. The division operation a / b becomes (a * modInverse(b)) % MOD. The modular inverse is calculated using modular exponentiation.
This approach computes the necessary factorials and their inverses on-the-fly for each word. While straightforward, it leads to redundant computations if the same factorial is needed for multiple words or character counts.
class Solution { private static final int MOD = 1_000_000_007; public int countAnagrams(String s) { String[] words = s.split(" "); long ans = 1; for (String word : words) { ans = (ans * calculatePermutations(word)) % MOD; } return (int) ans; } private long calculatePermutations(String word) { int len = word.length(); long permutations = factorial(len); int[] counts = new int[26]; for (char c : word.toCharArray()) { counts[c - 'a']++; } for (int count : counts) { if (count > 1) { long denominatorFact = factorial(count); long invDenominator = modInverse(denominatorFact); permutations = (permutations * invDenominator) % MOD; } } return permutations; } private long factorial(int n) { long res = 1; for (int i = 2; i <= n; i++) { res = (res * i) % MOD; } return res; } private long modInverse(long n) { return power(n, MOD - 2); } private long power(long base, long exp) { long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) { res = (res * base) % MOD; } base = (base * base) % MOD; exp /= 2; } return res; }}Complexity
Time
O(N + W * L_max * log(MOD)), where N is the length of `s`, W is the number of words, and L_max is the maximum length of a word. Splitting takes O(N). For each of the W words, we might compute factorials up to L_max, taking O(L_max) time, and perform up to 26 modular inverse calculations, each taking O(log(MOD)). In the worst case where W is proportional to N (e.g., many short words), this approaches O(N * log(MOD)).
Space
O(N), where N is the length of the input string `s`. This space is primarily used to store the array of words after splitting the string.
Trade-offs
Pros
Simple to understand and implement.
Does not require extra space for pre-computation tables.
Cons
Inefficient due to repeated calculations. The
factorial(k)function may be called multiple times with the same inputkfor different words or different character counts.Each call to
factorial(k)takesO(k)time, which can be slow if words are long.
This approach improves upon the first one by avoiding re-computation of factorials. Since the maximum length of any word (and any character count) is bounded by the total length of the string s, we can pre-calculate all necessary factorials once at the beginning and store them in an array.
First, we create a factorials array and populate it such that factorials[i] = i! % MOD. This takes O(N) time, where N is the length of s.
Then, when processing each word, instead of calling a factorial() function, we can retrieve the pre-computed values from the array in O(1) time. We still need to compute the modular inverse for each denominator term (fact[count]) on-the-fly using the power function. This optimization eliminates the redundant O(L) work for factorial calculations inside the main loop.
Algorithm
- Define
MOD = 10^9 + 7. - Pre-compute all factorials up to
s.length()and store them in an arrayfact.fact[i] = i! % MOD. - Implement
powerandmodInversefunctions as in the previous approach. - Split the input string
sinto words. - Initialize
totalAnagramsto 1. - Iterate through each
word: a. Get the lengthnand count character frequenciesc. b. Get the numeratorfact[n]from the pre-computed table. c. For each character countc > 1, calculate the inverse of its factorial:inv = modInverse(fact[c]). d. Multiply the numerator by this inverse:permutations = (permutations * inv) % MOD. e. Update the total count:totalAnagrams = (totalAnagrams * permutations) % MOD. - Return
totalAnagrams.
Walkthrough
To optimize the previous approach, we identify that factorial values are often re-calculated. We can eliminate this redundancy with pre-computation. We create an array, say fact, of size s.length() + 1. We fill this array such that fact[i] stores the value of i! modulo MOD.
This pre-computation step is done once. The main logic then proceeds as before: split the string into words and calculate permutations for each. However, when we need a factorial k!, we simply look it up in our fact array at index k. This is an O(1) operation.
The modular inverses of the denominator factorials are still computed as needed. This means for each word, we still loop through its character counts and call the modInverse function, which in turn calls the power function.
class Solution { private static final int MOD = 1_000_000_007; private long[] fact; public int countAnagrams(String s) { int n = s.length(); precomputeFactorials(n); String[] words = s.split(" "); long ans = 1; for (String word : words) { ans = (ans * calculatePermutations(word)) % MOD; } return (int) ans; } private void precomputeFactorials(int n) { fact = new long[n + 1]; fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; } } private long calculatePermutations(String word) { int len = word.length(); long permutations = fact[len]; int[] counts = new int[26]; for (char c : word.toCharArray()) { counts[c - 'a']++; } for (int count : counts) { if (count > 1) { long invDenominator = modInverse(fact[count]); permutations = (permutations * invDenominator) % MOD; } } return permutations; } private long modInverse(long n) { return power(n, MOD - 2); } private long power(long base, long exp) { long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) { res = (res * base) % MOD; } base = (base * base) % MOD; exp /= 2; } return res; }}Complexity
Time
O(N + W * log(MOD)), where N is the length of `s` and W is the number of words. Pre-computation takes O(N). The main loop iterates W times. Inside the loop, frequency counting takes O(L) (summing to O(N) over all words), and we perform up to 26 `modInverse` calls, each taking O(log(MOD)). The total is dominated by pre-computation and the inverse calculations.
Space
O(N), where N is the length of `s`. We need O(N) for the words array and O(N) for the `fact` array.
Trade-offs
Pros
More efficient than the direct approach by eliminating redundant factorial calculations.
Factorial lookups are O(1).
Cons
Still requires on-the-fly calculation of modular inverses for each denominator term, which involves the
powerfunction (O(log MOD)), making it slower than the fully pre-computed approach.Requires O(N) extra space for the factorials table.
This is the most efficient approach. It builds upon the second approach by pre-computing not only the factorials but also their modular inverses. This eliminates the need for any power function calls inside the main loop, making the calculation for each word extremely fast.
The process involves two pre-computation steps:
- Compute
fact[i] = i! % MODforifrom 0 toN. - Compute
invFact[i] = (i!)⁻¹ % MOD. This is done by first calculatinginvFact[N]using thepowerfunction once. Then, we can find the other inverse factorials iteratively using the property(k!)⁻¹ = ((k+1)!)⁻¹ * (k+1). We iterate fromN-1down to 0 to populate theinvFactarray.
After this O(N) pre-computation, calculating the permutations for any word involves only array lookups and multiplications, which are O(1) operations. This makes the main loop very fast.
Algorithm
- Define
MOD = 1_000_000_007. - Pre-compute factorials up to
s.length()in an arrayfact. - Pre-compute the modular inverse of each factorial and store them in an array
invFact. This can be done efficiently: a. CalculateinvFact[n]asmodInverse(fact[n])using thepowerfunction once. b. Use the relation(k!)⁻¹ = ((k+1)!)⁻¹ * (k+1)to compute the rest of the inverse factorials by iterating downwards:invFact[i] = (invFact[i+1] * (i+1)) % MOD. - Split the input string
sinto words. - Initialize
totalAnagramsto 1. - Iterate through each
word: a. Get lengthnand count character frequenciesc. b. Start withpermutations = fact[n]. c. For each character countc > 1, multiply by the pre-computed inverse factorial:permutations = (permutations * invFact[c]) % MOD. d. Update the total count:totalAnagrams = (totalAnagrams * permutations) % MOD. - Return
totalAnagrams.
Walkthrough
The key to this optimal approach is to pre-calculate everything possible. The permutation formula n! / (c1! * c2! * ...) can be rewritten as n! * (c1!)⁻¹ * (c2!)⁻¹ * ... in modular arithmetic. This means we need factorials and their inverses.
We pre-compute two arrays:
fact:fact[i]storesi! % MOD.invFact:invFact[i]stores(i!)⁻¹ % MOD.
Computing fact is straightforward. To compute invFact efficiently, we first compute the inverse of the largest factorial we need, fact[N], using the power function. This takes O(log MOD). Then, we use the recurrence invFact[i] = invFact[i+1] * (i+1) % MOD to compute the rest of the values in O(N) time by iterating backwards.
With both fact and invFact arrays ready, processing each word becomes a series of lookups. For a word of length n with character counts c_i, the number of permutations is fact[n] * invFact[c1] * invFact[c2] * ... % MOD. Each of these operations is O(1).
class Solution { private static final int MOD = 1_000_000_007; private long[] fact; private long[] invFact; public int countAnagrams(String s) { int n = s.length(); precomputeFactorials(n); String[] words = s.split(" "); long ans = 1; for (String word : words) { ans = (ans * calculatePermutations(word)) % MOD; } return (int) ans; } private void precomputeFactorials(int n) { fact = new long[n + 1]; invFact = new long[n + 1]; fact[0] = 1; invFact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; } invFact[n] = power(fact[n], MOD - 2); for (int i = n - 1; i >= 1; i--) { invFact[i] = (invFact[i + 1] * (i + 1)) % MOD; } } private long calculatePermutations(String word) { int len = word.length(); long permutations = fact[len]; int[] counts = new int[26]; for (char c : word.toCharArray()) { counts[c - 'a']++; } for (int count : counts) { if (count > 1) { permutations = (permutations * invFact[count]) % MOD; } } return permutations; } private long power(long base, long exp) { long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) { res = (res * base) % MOD; } base = (base * base) % MOD; exp /= 2; } return res; }}Complexity
Time
O(N), where N is the length of `s`. The pre-computation of both `fact` and `invFact` takes O(N + log(MOD)). Processing all words takes O(N) because it's just frequency counting and lookups. The overall complexity is linear in the length of the string.
Space
O(N), where N is the length of `s`. We need O(N) for the words array, O(N) for `fact`, and O(N) for `invFact`.
Trade-offs
Pros
Most efficient approach with the best time complexity.
All calculations for permutations after pre-computation are extremely fast (O(1) lookups).
Cons
Requires more space than other approaches due to storing two arrays (
factandinvFact).The pre-computation logic is slightly more complex.
Solutions
Solution
import java.math.BigInteger ; class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int countAnagrams ( String s ) { int n = s . length (); long [] f = new long [ n + 1 ]; f [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; } long p = 1 ; for ( String w : s . split ( " " )) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < w . length (); ++ i ) { ++ cnt [ w . charAt ( i ) - 'a' ]; } p = p * f [ w . length ()] % MOD ; for ( int v : cnt ) { p = p * BigInteger . valueOf ( f [ v ]). modInverse ( BigInteger . valueOf ( MOD )). intValue () % MOD ; } } return ( int ) p ; } }class Solution {public: const int mod = 1e9 + 7; int countAnagrams(string s) { stringstream ss(s); string w; long ans = 1, mul = 1; while (ss >> w) { int cnt[26] = {0}; for (int i = 1; i <= w.size(); ++i) { int c = w[i - 1] - 'a'; ++cnt[c]; ans = ans * i % mod; mul = mul * cnt[c] % mod; } } return ans * pow(mul, mod - 2) % mod; } long pow(long x, int n) { long res = 1L; for (; n; n /= 2) { if (n % 2) res = res * x % mod; x = x * x % mod; } return res; }};mod = 10 ** 9 + 7 f = [ 1 ] for i in range ( 1 , 10 ** 5 + 1 ): f . append ( f [ - 1 ] * i % mod ) class Solution : def countAnagrams ( self , s : str ) -> int : ans = 1 for w in s . split (): cnt = Counter ( w ) ans *= f [ len ( w )] ans %= mod for v in cnt . values (): ans *= pow ( f [ v ], - 1 , mod ) ans %= mod return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.