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.
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 ; } }Video 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.