LeetCode 2514 - Count Anagrams

Difficulty: 🔴 Hard
Topics: Hash Table, Math, String, Combinatorics, Counting

Solution

Problem Understanding

The problem asks us to count how many distinct anagram sentences can be formed from a given string s.

The input string contains one or more words separated by single spaces. An anagram sentence must preserve the structure of the original sentence. Specifically, the i-th word in the new sentence must be a permutation of the i-th word in the original sentence.

For example:

"abc def" can become "bca fed"
"abc def" cannot become "def abc" because words cannot change positions
"abc" has 3! = 6 permutations
"aa" has only 1 distinct permutation because swapping identical characters does not create a new string

The final answer is the product of the number of distinct permutations for each word independently.

The constraints are very important:

s.length <= 10^5
Words may be long
There may be many repeated characters

A brute-force permutation generation approach is completely impossible because factorial growth becomes enormous even for moderate word sizes.

The problem is fundamentally a combinatorics problem. For a word of length n:

Total permutations: n!
If characters repeat, divide by factorials of duplicate frequencies

The number of distinct permutations is:

$$\frac{n!}{f_1! \cdot f_2! \cdot \dots \cdot f_k!}$$

where f_i are character frequencies.

Since the answer can become extremely large, we must compute everything modulo:

$$10^9 + 7$$

This modulus is prime, which allows modular inverses using Fermat's Little Theorem.

Important edge cases include:

A single word
Words with all identical letters
Many small words
Very large words
Words where every character is unique
Maximum input size requiring efficient preprocessing

Approaches

Brute Force Approach

A naive solution would generate every permutation of every word, remove duplicates, and count how many unique strings remain.

For example, for "too":

Generate permutations:
"too"
"oto"
"oot"
duplicates from swapping identical 'o'

Then combine permutations across words.

This approach is correct because it explicitly enumerates all possible anagrams. However, it is computationally infeasible.

A word of length 10 already has:

$$10! = 3,628,800$$

permutations.

With input sizes up to 10^5, brute force is impossible both in time and memory.

Optimal Approach

The key observation is that we never need to generate permutations explicitly.

For each word:

$$\text{distinct permutations} = \frac{n!}{\prod f_i!}$$

We compute this efficiently using:

Precomputed factorials
Modular inverses
Frequency counting

Since words are independent, the total answer is simply the product of each word's count.

Because the modulus is prime, division modulo MOD can be performed using modular inverse:

$$a^{-1} \equiv a^{MOD-2} \pmod{MOD}$$

This allows the entire computation to run in linear time relative to the input size.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Explicitly generates permutations
Optimal	O(n)	O(n)	Uses combinatorics and modular arithmetic

Algorithm Walkthrough

Step 1: Split the sentence into words

We process each word independently because permutations of one word do not affect another word.

For example:

"too hot"

becomes:

["too", "hot"]

Step 2: Precompute factorials

We need factorials repeatedly:

$$0!, 1!, 2!, \dots, n!$$

where n is the maximum possible word length.

Instead of recomputing factorials repeatedly, we precompute them once.

We store:

factorial[i] = i! % MOD

Step 3: Process each word

For every word:

Count character frequencies using a hash map
Compute:

$$\text{ways} = n!$$

Divide by each repeated frequency factorial:

$$\text{ways} \div f_i!$$

Since division modulo is not directly allowed, we multiply by modular inverses.

Step 4: Compute modular inverses

Using Fermat's Little Theorem:

$$a^{-1} \equiv a^{MOD-2} \pmod{MOD}$$

So:

pow(x, MOD - 2, MOD)

computes the modular inverse of x.

Step 5: Multiply results together

Each word contributes independently:

$$\text{answer} = \prod \text{word_ways}$$

Take modulo after every multiplication.

Why it works

For a word of length n, there are initially n! arrangements.

If a character appears multiple times, swapping identical copies does not create distinct permutations. Therefore, we divide by the factorial of each repeated count.

Because each word can be permuted independently, the multiplication principle applies. Multiplying the counts for all words gives the total number of valid anagram sentences.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def countAnagrams(self, s: str) -> int:
        MOD = 10**9 + 7
        
        words = s.split()
        max_len = max(len(word) for word in words)
        
        # Precompute factorials
        factorial = [1] * (max_len + 1)
        for i in range(1, max_len + 1):
            factorial[i] = factorial[i - 1] * i % MOD
        
        answer = 1
        
        for word in words:
            length = len(word)
            
            # Total permutations = length!
            ways = factorial[length]
            
            # Divide by factorial(freq) for duplicates
            freq = Counter(word)
            
            for count in freq.values():
                inverse = pow(factorial[count], MOD - 2, MOD)
                ways = ways * inverse % MOD
            
            answer = answer * ways % MOD
        
        return answer

The implementation begins by splitting the sentence into words. Since each word is processed independently, this simplifies the problem considerably.

Next, factorials are precomputed up to the maximum word length. This allows constant time factorial lookup during processing.

For each word, we compute the total number of permutations as length!. We then count character frequencies using Counter.

If a character appears multiple times, we divide by freq!. Because modular arithmetic does not support direct division, we multiply by the modular inverse instead.

Finally, the number of arrangements for each word is multiplied into the global answer.

Go Solution

package main

import (
	"strings"
)

const MOD int64 = 1_000_000_007

func modPow(base, exp int64) int64 {
	result := int64(1)

	for exp > 0 {
		if exp%2 == 1 {
			result = result * base % MOD
		}

		base = base * base % MOD
		exp /= 2
	}

	return result
}

func countAnagrams(s string) int {
	words := strings.Split(s, " ")

	maxLen := 0
	for _, word := range words {
		if len(word) > maxLen {
			maxLen = len(word)
		}
	}

	// Precompute factorials
	factorial := make([]int64, maxLen+1)
	factorial[0] = 1

	for i := 1; i <= maxLen; i++ {
		factorial[i] = factorial[i-1] * int64(i) % MOD
	}

	answer := int64(1)

	for _, word := range words {
		ways := factorial[len(word)]

		freq := make(map[byte]int)

		for i := 0; i < len(word); i++ {
			freq[word[i]]++
		}

		for _, count := range freq {
			inverse := modPow(factorial[count], MOD-2)
			ways = ways * inverse % MOD
		}

		answer = answer * ways % MOD
	}

	return int(answer)
}

The Go implementation follows the same mathematical approach as the Python version.

Instead of Python's built in pow(..., mod) support, Go requires an explicit fast exponentiation function for modular power computation.

Go also uses int64 to avoid overflow during multiplication before modulo reduction.

Character frequencies are stored using map[byte]int, since the input only contains lowercase English letters.

Worked Examples

Example 1

Input: s = "too hot"

Split into words:

["too", "hot"]

Processing `"too"`

Character	Frequency
t	1
o	2

Length:

Total permutations:

$$3! = 6$$

Duplicate adjustment:

$$\frac{6}{2!} = \frac{6}{2} = 3$$

Distinct permutations:

too
oto
oot

Processing `"hot"`

Character	Frequency
h	1
o	1
t	1

Total permutations:

$$3! = 6$$

No duplicates exist.

Ways:

Final Answer

$$3 \times 6 = 18$$

Output:

Example 2

Input: s = "aa"

Frequency table:

Character	Frequency
a	2

Total permutations:

$$2! = 2$$

Duplicate adjustment:

$$\frac{2}{2!} = 1$$

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed a constant number of times
Space	O(n)	Factorial table and frequency maps

The preprocessing step computes factorials once up to the maximum word length. Every character in the input participates in frequency counting exactly once.

Modular inverse computation uses logarithmic exponentiation, but the alphabet size is fixed at 26 lowercase letters, so the total contribution remains linear overall.

Test Cases

sol = Solution()

assert sol.countAnagrams("too hot") == 18  # Example with duplicates
assert sol.countAnagrams("aa") == 1  # All identical characters
assert sol.countAnagrams("abc") == 6  # All unique characters
assert sol.countAnagrams("a") == 1  # Single character
assert sol.countAnagrams("ab ba") == 4  # Multiple independent words
assert sol.countAnagrams("aaa bbb") == 1  # No distinct rearrangements
assert sol.countAnagrams("abcd") == 24  # 4! permutations
assert sol.countAnagrams("aab") == 3  # 3! / 2!
assert sol.countAnagrams("aabb") == 6  # 4! / (2! * 2!)
assert sol.countAnagrams("abc def ghi") == 216  # 6 * 6 * 6
assert sol.countAnagrams("zzzzzz") == 1  # Large repeated block
assert sol.countAnagrams("abab") == 6  # Duplicate pairs

Test	Why
`"too hot"`	Validates duplicate handling across multiple words
`"aa"`	Validates identical characters
`"abc"`	Validates pure factorial case
`"a"`	Smallest possible input
`"ab ba"`	Ensures words are independent
`"aaa bbb"`	Multiple words with only one arrangement
`"abcd"`	Larger factorial computation
`"aab"`	Single duplicated character
`"aabb"`	Multiple duplicated groups
`"abc def ghi"`	Product of several words
`"zzzzzz"`	Extreme repetition
`"abab"`	Non-adjacent duplicates

Edge Cases

One important edge case is a word where every character is identical, such as "aaaaaa". A naive implementation might incorrectly return 6!, even though all permutations are identical. The formula correctly divides by 6!, producing exactly 1.

Another important case is words with all unique characters, such as "abcdef". In this situation, there are no duplicate adjustments, so the result should simply be 6!. The implementation naturally handles this because every frequency is 1, and dividing by 1! changes nothing.

A third critical edge case is very large inputs near the constraint limit. Since s.length can reach 10^5, repeatedly recomputing factorials or generating permutations would timeout. Precomputing factorials once and processing characters linearly ensures the algorithm remains efficient even at maximum scale.

LeetCode 2514 - Count Anagrams

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Step 1: Split the sentence into words

Step 2: Precompute factorials

Step 3: Process each word

Step 4: Compute modular inverses

Step 5: Multiply results together

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Processing "too"

Processing "hot"

Final Answer

Example 2

Complexity Analysis

Test Cases

Edge Cases

Processing `"too"`

Processing `"hot"`