2514. Count Anagrams

HardHash TableMathStringCombinatoricsCounting
Leetcode Link

Problem Description

The problem gives you a string s which consists of one or more words separated by single spaces. A string t is considered an anagram of string s if for every word in t, there is a corresponding word in s that has exactly the same letters, but possibly in a different order. The goal is to calculate the number of distinct anagrams of s. Since the result could be a very large number, you're asked to return this number modulo 10^9 + 7, which is often used in programming contests to avoid dealing with exceedingly large numbers that could cause overflow errors.

Intuition

To solve this problem, we need to think about what an anagram actually is. An anagram of a word is a permutation of its letters. If we consider each word separately, the number of different permutations (and thus anagrams) for a word is given by the factorial of the length of the word.

However, there's a catch: if a word has duplicate letters, we must divide the total count by the factorials of the counts of each letter. That's because permuting the duplicates among themselves doesn't create unique anagrams.

For example, for the word "aabb", it has 4 letters, so naïvely we might think there are 4! (which is 24) anagrams. However, both 'a' and 'b' are repeated twice. We need to divide 4! by the number of permutations of 'a' (which is 2!) and by the number of permutations of 'b' (which is 2!) to get the right answer: 4! / (2! * 2!), which equals 6.

The solution code first builds a list f of precomputed factorials modulo 10^9 + 7 to avoid recalculating factorials for each word, thereby saving time.

Then, for each word in the given string, we calculate the factorial of the length of the word, multiply this by the resulting ans so far, and then modify ans by multiplying it by the modular inverses of the factorials of the counts of each letter in the word. The function pow(f[v], -1, mod) is used to compute the modular inverse of f[v] under the modulo 10^9 + 7.

Finally, we return ans, which—because we've taken the modulo at each step—will be the correct count of distinct anagrams of s modulo 10^9 + 7.

Learn more about Math and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

Solution Approach

The provided solution code implements the following approach:

  1. Precompute Factorials: Initially, the code precomputes factorials of numbers up to 10^5 and stores them in a list f. This list will be used to look up the factorial of any number during the computation without having to recalculate it. This precomputation is done modulo 10^9 + 7 to prevent integer overflow and to comply with the requirement of returning the answer modulo 10^9 + 7.

  2. Iterate Over Words: The core logic of the solution iterates over each word within the input string s. We use the split() method to break the string into a list of words.

  3. Count Letter Frequencies: For each word, a Counter (from Python's collections module) is used to calculate the frequencies of each letter within the word. The counter creates a dictionary that maps each letter to its frequency.

  4. Calculate Anagrams: For every word, we first multiply ans with the factorial of the length of the word. This represents the total number of permutations of the letters without considering duplicate letters.

  5. Adjust for Duplicate Letters: Since we need to account for repeated letters, we loop over the values of our letter frequency counter and get the factorial of each letter count. Using the precomputed factorials in f, we calculate the modular inverse of these factorials using the pow function, which allows us to compute inverse modulo operations. We then multiply ans by this inverse to correctly account for the permutations of the duplicate letters.

  6. Keep Result within Modulo: Throughout these operations, we ensure that ans is kept within the modulo 10^9 + 7 by taking the modulo operation after each multiplication. This step is crucial because it ensures that the value of ans never exceeds the limit where it might cause overflow errors.

  7. Return the Result: After iterating through all the words and updating ans accordingly, we return ans, which is the total number of distinct anagrams of the original string s modulo 10^9 + 7.

It's worth noting that the pow(x, -1, mod) computation is a way of finding the modular multiplicative inverse of x mod mod when x and mod are coprime (which they are in this case because the mod is prime and the factorial is not zero).

Using this approach, the solution code efficiently calculates the number of distinct anagrams of the given string s by breaking the problem down into calculations involving factorials and considering the impact of duplicate letters.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the string s = "abc cab".

Step 1: Precompute Factorials

Factorials up to the maximum length 10^5 are precomputed and stored in a list f modulo 10^9 + 7. For this example, we would have f[0] = 1, f[1] = 1, f[2] = 2, f[3] = 6, ... and so on.

Step 2: Iterate Over Words

We split the string s into words using the .split() method, resulting in the list ["abc", "cab"].

Step 3: Count Letter Frequencies

For each word, we count letter frequencies. For abc, it's {'a': 1, 'b': 1, 'c': 1}. For cab, it's the same since cab is a permutation of abc.

Step 4: Calculate Anagrams

We start with ans = 1. For each word:

  • For the word abc, the length is 3, so we multiply ans by f[3] which is 6. Now, ans=ans * 6 % (10^9 + 7)->ans` = 6. We don't need to adjust for duplicates because all letters are distinct.

  • For the word cab, we repeat the process. Multiplying ans by f[3] which is 6, we get ans = 36 modulo 10^9 + 7.

Step 5: Adjust for Duplicate Letters

Both words in our example do not have duplicate letters, so we don't need to adjust for duplicates. If there were duplicates, we would multiply ans by the modular inverses of the factorials of the letter counts.

Step 6: Keep Result within Modulo

This step ensures that ans remains within the range allowed by modulo 10^9 + 7. In our case, since ans is 36 after processing both words, there is no issue with overflow, and we don't need further modulo operations here.

Step 7: Return the Result

We have completed the iteration over all words, and the final ans represents the total number of distinct anagrams of the string s modulo 10^9 + 7. So we would return ans = 36.

That number, 36, says that there are 36 different permutations of s considering each word and its anagrams, but this is only for the length and uniqueness of the chosen words "abc" and "cab". In a more complex example with longer words and repeating characters, steps 4 and 5 would show more adjustment for duplicates.

Solution Implementation

1from collections import Counter
2
3MOD = 10**9 + 7
4
5# Pre-calculate factorial values modulo MOD
6factorials = [1]
7for i in range(1, 10**5 + 1):
8    new_value = factorials[-1] * i % MOD
9    factorials.append(new_value)
10
11class Solution:
12    def countAnagrams(self, s: str) -> int:
13        # Initialize the answer as 1
14        answer = 1
15      
16        # Split the string into words
17        for word in s.split():
18            # Count the frequency of each character in the word
19            character_counts = Counter(word)
20            # Multiply the answer by the factorial of the length of the word
21            answer *= factorials[len(word)]
22            answer %= MOD
23          
24            # For each character, update the answer by multiplying with
25            # the multiplicative inverse of the factorial of the character's count
26            for count in character_counts.values():
27                answer *= pow(factorials[count], -1, MOD)
28                answer %= MOD
29      
30        return answer
31
32# Example usage:
33# sol = Solution()
34# result = sol.countAnagrams("the quick brown fox")
35# print(result)
36
1import java.math.BigInteger;
2
3class Solution {
4    // Define the modulus constant for taking the mod of large numbers to prevent overflow
5    private static final int MOD = (int) 1e9 + 7;
6
7    // Method to count the number of anagrams for groups of words separated by spaces
8    public int countAnagrams(String s) {
9        int length = s.length();
10        // Factorial array to store precomputed factorials under MOD
11        long[] factorials = new long[length + 1];
12        factorials[0] = 1; // 0! is 1
13      
14        // Calculate factorial for each number up to length, with mod
15        for (int i = 1; i <= length; ++i) {
16            factorials[i] = (factorials[i - 1] * i) % MOD;
17        }
18      
19        long product = 1; // Initialize the product to 1
20        // Split the given string by spaces and process each group of characters
21        for (String word : s.split(" ")) {
22            int[] characterCount = new int[26];
23          
24            // Count the frequency of each character in the current word
25            for (int i = 0; i < word.length(); ++i) {
26                characterCount[word.charAt(i) - 'a']++;
27            }
28          
29            // Multiply the product by the factorial of the length of the word
30            product = (product * factorials[word.length()]) % MOD;
31          
32            // Iterating over the character frequencies,
33            // taking the modInverse of their factorial, and updating the product
34            for (int count : characterCount) {
35                if (count > 0) {
36                    BigInteger factorial = BigInteger.valueOf(factorials[count]);
37                    BigInteger modInverse = factorial.modInverse(BigInteger.valueOf(MOD));
38                    product = (product * modInverse.intValue()) % MOD;
39                }
40            }
41        }
42        // Finally, return the product casted to an integer
43        return (int) product;
44    }
45}
46
1#include <sstream>
2#include <string>
3
4class Solution {
5public:
6    // We declare 'mod' as a static constant because it's a property of the class and
7    // should not change.
8    static const int MOD = 1e9 + 7;
9
10    // Calculate the number of anagrams for words in a string
11    // Break down the string into words and compute the result
12    int countAnagrams(std::string s) {
13        std::stringstream ss(s);  // used to break the string into words
14        std::string word;         // to store each word individually
15        long ans = 1;             // to store the number of permutations
16        long factorial = 1;       // to store the factorial part
17
18        // Process each word in the string
19        while (ss >> word) {
20            int count[26] = {0};  // to count occurrences of each letter
21
22            for (int i = 1; i <= word.size(); ++i) {
23                // Calculate zero-based index for character in alphabet
24                int charIndex = word[i - 1] - 'a';
25
26                // Increment the count for this character
27                ++count[charIndex];
28
29                // Update the permutation count: ans = ans * i
30                ans = (ans * i) % MOD;
31
32                // Update the factorial part using the letter's occurrence
33                factorial = (factorial * count[charIndex]) % MOD;
34            }
35        }
36
37        // Use modular inverse to divide ans by the factorial part
38        return static_cast<int>((ans * pow(factorial, MOD - 2)) % MOD);
39    }
40
41    // Calculate x raised to the power of n mod MOD using fast exponentiation
42    long pow(long x, int n) {
43        long result = 1L;  // start with result as 1
44
45        // Continue looping until n becomes zero
46        while (n > 0) {
47            // If n is odd, multiply the result by x
48            if (n % 2 == 1) {
49                result = (result * x) % MOD;
50            }
51
52            // Square x and reduce n by half
53            x = (x * x) % MOD;
54            n /= 2;
55        }
56
57        return result;
58    }
59};
60
1// Define the modulo constant.
2const MOD: number = 1e9 + 7;
3
4// Calculate the number of anagrams for words in a string.
5// Break down the string into words and compute the result.
6function countAnagrams(s: string): number {
7    const words: string[] = s.split(/\s+/); // Split the string into words
8    let ans: number = 1; // To store the number of permutations
9    let factorial: number = 1; // To store the factorial part
10
11    // Process each word in the string
12    for (let word of words) {
13        let count: number[] = new Array(26).fill(0); // To count occurrences of each letter
14
15        for (let i: number = 0; i < word.length; i++) {
16            // Calculate zero-based index for character in alphabet
17            let charIndex: number = word.charCodeAt(i) - 'a'.charCodeAt(0);
18
19            // Increment the count for this character
20            count[charIndex]++;
21
22            // Update the permutation count: ans = ans * (i + 1)
23            ans = (ans * (i + 1)) % MOD;
24
25            // Update the factorial part using the letter's occurrence
26            factorial = (factorial * count[charIndex]) % MOD;
27        }
28    }
29
30    // Use modular inverse to divide ans by the factorial part
31    return (ans * pow(factorial, MOD - 2)) % MOD;
32}
33
34// Calculate x raised to the power of n mod MOD using fast exponentiation.
35function pow(x: number, n: number): number {
36    let result: number = 1; // Start with result as 1
37
38    // Continue looping until n becomes zero.
39    while (n > 0) {
40        // If n is odd, multiply the result by x.
41        if (n % 2 === 1) {
42            result = (result * x) % MOD;
43        }
44
45        // Square x and reduce n by half.
46        x = (x * x) % MOD;
47        n = Math.floor(n / 2);
48    }
49
50    return result;
51}
52
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

Time Complexity

The time complexity of the precomputation part (where the factorials are computed up to 10**5) is O(N) where N is 10**5. This part is run only once, and each operation is a multiplication and a modulo operation, which are both O(1). When analyzing the countAnagrams method, for each word in the input string s, the code counts the frequency of characters, which is O(K) where K is the length of the word. Multiplying by the factorial of the length of the word is O(1) since we have precomputed the factorials. The for loop for dividing by the factorial of the count of each character runs at most 26 times (since there are only 26 letters in the alphabet), and each iteration does a modular inverse and multiplication, which can both be considered O(1) under modular arithmetic. Therefore, for each word, the complexity is dominated by O(K). Since this is done for every word in the string, and if there are W words in s, the overall time complexity of countAnagrams is O(W*K).

Space Complexity

The space complexity for storing the precomputed factorials is O(N), where N is 10**5. Aside from that, the space used by the function countAnagrams depends on the size of the counter object, which is at most 26 for each word. Therefore, the space complexity for the function countAnagrams is O(1), making the total space complexity of the program O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫