#2514

Hard

LeetCode Problem Workspace

Count Anagrams

Learn to count distinct anagrams for a multi-word string using hash tables, math, and combinatorics efficiently.

hash table math string combinatorics counting

Problem Statement

Given a string s composed of one or more words separated by single spaces, compute how many distinct anagrams of s exist. Each word in the anagram must be a permutation of the corresponding word in s.

Return the total number of distinct anagrams modulo 10^9 + 7. Words may contain repeated characters, so careful counting using combinatorial math is required to avoid overcounting identical permutations.

Examples

Example 1

Input: s = "too hot"

Output: 18

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

There is only one anagram possible for the given string.

Constraints

1 <= s.length <= 105
s consists of lowercase English letters and spaces ' '.
There is single space between consecutive words.

Solution Approach

Split and Analyze Words

Divide the string into individual words and use a hash table to count the frequency of each character in every word. This sets up accurate permutation calculations that handle repeated letters.

Compute Word-Level Permutations

For each word, calculate the factorial of its length divided by the factorial of each character count. Apply modular arithmetic at each step to prevent overflow while counting distinct permutations correctly.

Combine Results Across Words

Multiply the number of permutations for each word to get the total number of anagrams for the entire string. Return the final result modulo 10^9 + 7 to satisfy the problem constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on computing factorials and iterating over each character in all words, typically O(n + sum(word lengths)) where n is string length. Space complexity is O(k) per word for character counts, with k up to 26 for lowercase letters.

What Interviewers Usually Probe

Emphasize efficient counting over generating all permutations.
Check if the candidate handles repeated characters correctly with combinatorial formulas.
Look for proper use of modulo arithmetic to avoid integer overflow.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all permutations explicitly, which causes TLE for long strings.
Ignoring repeated letters and overcounting identical permutations.
Multiplying large factorials without modulo, causing overflow.

Follow-up variants

Count anagrams of a single long word with repeated characters.
Compute anagrams where only a subset of words can be permuted.
Find the lexicographically smallest or largest anagram instead of the count.

FAQ

What is the main pattern in Count Anagrams?

The problem uses a Hash Table plus Math pattern, focusing on counting character frequencies and computing factorial-based permutations.

Why is modular arithmetic needed in this problem?

Because the number of distinct anagrams can be very large, all intermediate and final calculations must be done modulo 10^9 + 7 to prevent overflow.

Can I generate all permutations to count them?

Generating all permutations is inefficient and will exceed time limits; use combinatorial counting with hash tables instead.

How do repeated letters affect the solution?

Repeated letters reduce the total number of unique permutations, so factorials must be divided by the factorial of each letter count.

What is an efficient approach for multi-word strings?

Compute permutations for each word separately using character counts, then multiply the results together with modulo arithmetic for the total count.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countAnagrams(self, s: str) -> int:
        mod = 10**9 + 7
        ans = mul = 1
        for w in s.split():
            cnt = Counter()
            for i, c in enumerate(w, 1):
                cnt[c] += 1
                mul = mul * cnt[c] % mod
                ans = ans * i % mod
        return ans * pow(mul, -1, mod) % mod

Continue Practicing

#3518 smallest palindromic rearrangement ii #2842 count k subsequences of a string with maximum beauty #3128 right triangles