We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Anagrams

Difficulty: Hard

Problem Description

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 i-th word of t is a permutation of the i-th word of s. Return the number of distinct anagrams of s. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • Anagrams of a string can be counted using the factorial of the length of the string divided by the factorial of the counts of each character.
  • Spaces between words should be handled as they separate different groups of characters.
  • To compute the number of distinct anagrams per word, we need to calculate the factorial of the length of each word and divide it by the factorial of the counts of each unique character.
  • The overall result is the product of the distinct anagrams for each word.

Space and Time Complexity

Time Complexity: O(n) for counting characters and computing factorials, where n is the length of the string.
Space Complexity: O(k), where k is the number of unique characters.

Solution

To solve the problem, we will:

  1. Split the input string into individual words.
  2. For each word, calculate the frequency of each character.
  3. Use the character frequencies to compute the number of distinct anagrams for that word using the formula:
    number of anagrams = (length of word)! / (product of frequencies of each character)!
  4. Compute the factorial values and their modular inverses to handle large numbers efficiently.
  5. Multiply the number of anagrams for each word to get the final result.

We will use a hash table (dictionary) to keep track of character counts and a combinatorial approach to compute the factorials.

Code Solutions

MOD = 10**9 + 7

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result = (result * i) % MOD
    return result

def mod_inverse(x):
    return pow(x, MOD - 2, MOD)

def count_anagrams(s):
    words = s.split()
    total_anagrams = 1
    
    for word in words:
        char_count = {}
        for char in word:
            char_count[char] = char_count.get(char, 0) + 1
        
        word_length = len(word)
        word_factorial = factorial(word_length)
        divisor = 1
        
        for count in char_count.values():
            divisor = (divisor * factorial(count)) % MOD
        
        total_anagrams = (total_anagrams * word_factorial * mod_inverse(divisor)) % MOD
    
    return total_anagrams

# Example usage
print(count_anagrams("too hot"))  # Output: 18
← Back to All Questions