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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Anagrams

Number: 2605

Difficulty: Hard

Paid? No

Companies: Amazon, MathWorks

Problem Description

Given a string s containing one or more words separated by a single space, count the number of distinct anagrams of s. Two strings are considered anagrams if, for every position, the word in one string can be reordered (permuted) to form the corresponding word in the other string. The answer may be very large, so it must be returned modulo 10^9 + 7.

Key Insights

  • Each word in the string can be rearranged independently.
  • For a given word, to compute the number of distinct permutations while accounting for duplicate letters, use the multinomial formula: factorial(length) divided by the product of factorials for each letter’s frequency.
  • The overall answer is the product of the results for each word, modulo 10^9 + 7.
  • Precomputation of factorials and modular inverses is useful when handling factorial division modulo a prime number.
  • Use Fermat’s Little Theorem for computing modular inverses under a prime modulus.

Space and Time Complexity

Time Complexity: O(n + m) where n is the total length of the input string and m is the sum of distinct letters in each word.
Space Complexity: O(L) where L is the length of the longest word (for precomputing factorials up to L) plus additional space needed for frequency counters.

Solution

The solution involves splitting the string into words and processing each word individually. For every word:

  1. Compute the factorial of its length (n!).
  2. For each letter with frequency f in the word, divide by f! modulo 10^9+7.
  3. Multiply the result for that word with a running product that holds results for previous words.

To handle division modulo 10^9+7, we precompute factorials up to the maximum word length and their modular inverses using Fermat's Little Theorem. The main data structures used are frequency counters (hash tables) and arrays for precomputed factorials.

Code Solutions

# Python solution for "Count Anagrams"

MOD = 10**9 + 7

# Function to compute x^y mod MOD using fast exponentiation
def mod_pow(x, y, mod):
    result = 1
    while y:
        if y & 1:
            result = (result * x) % mod
        x = (x * x) % mod
        y //= 2
    return result

# Function to compute modular inverse using Fermat's Little Theorem.
def mod_inverse(x, mod):
    return mod_pow(x, mod - 2, mod)

# Precompute factorials and inverse factorials up to max_n.
def precompute_factorials(max_n, mod):
    factorial = [1] * (max_n + 1)
    inv_factorial = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        factorial[i] = factorial[i - 1] * i % mod
    inv_factorial[max_n] = mod_inverse(factorial[max_n], mod)
    for i in range(max_n, 0, -1):
        inv_factorial[i - 1] = inv_factorial[i] * i % mod
    return factorial, inv_factorial

def countAnagrams(s):
    words = s.split()
    # Determine the maximum length among words for factorial precomputation
    max_len = max(len(word) for word in words)
    factorial, inv_factorial = precompute_factorials(max_len, MOD)
    
    ans = 1
    for word in words:
        n = len(word)
        # Start with n! for the number of permutations of the word.
        count = factorial[n]
        # Count frequency of each letter in the word.
        frequency = {}
        for ch in word:
            frequency[ch] = frequency.get(ch, 0) + 1
        # Divide by factorial of counts for duplicate letters.
        for freq in frequency.values():
            count = (count * inv_factorial[freq]) % MOD
        ans = (ans * count) % MOD
    return ans

# Example usage:
s = "too hot"
print(countAnagrams(s))  # Expected output: 18
← Back to All Questions