Count Anagrams - Practice Coding Problems

Count Anagrams - Problem

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.

For example, "acb dfe" is an anagram of "abc def", but "def cab" and "adc bef" are not.

Return the number of distinct anagrams of s. Since the answer may be very large, return it modulo 10^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: s = "ab"

› Output: 2

💡 Note: The word "ab" can be rearranged as "ab" and "ba", giving us 2 distinct anagrams.

Example 2 — Two Words

$ Input: s = "ab cd"

› Output: 4

💡 Note: Word "ab" has 2 permutations: "ab", "ba". Word "cd" has 2 permutations: "cd", "dc". Total anagrams = 2 × 2 = 4.

Example 3 — Repeated Characters

$ Input: s = "aab"

› Output: 3

💡 Note: The word "aab" can be arranged as "aab", "aba", "baa". Using formula: 3! / 2! = 6 / 2 = 3.

Constraints

1 ≤ s.length ≤ 1000
s contains only lowercase English letters and spaces
s does not have leading or trailing spaces
Every consecutive pair of words is separated by a single space

Visualization

Tap to expand

Understanding the Visualization

Input

String with words separated by spaces

Process

Calculate anagram count for each word using mathematical formula

Output

Product of all word anagram counts

Key Takeaway

🎯 Key Insight: Use the permutation formula n! / (product of factorial of frequencies) to avoid generating actual permutations

Asked in

G Google 12 f Facebook 8

The key insight is to use the mathematical formula for permutations with repetitions: n! / (freq1! × freq2! × ... × freqk!) for each word, then multiply the results. The optimal approach uses frequency counting and factorial calculations with modular arithmetic. Time: O(n × k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula (Optimal)	O(n × k)	O(1)	Use factorial formula to calculate permutations with repetitions
Generate All Permutations	O(n! × k)	O(n! × k)	Generate all possible permutations for each word and count them

Mathematical Formula (Optimal) — Algorithm Steps

Split string into words
For each word, count character frequencies
Apply permutation formula: n! / (product of factorials)
Multiply results for all words

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

For each word, count how many times each character appears

Apply Formula

Use n! / (freq1! × freq2! × ... × freqk!) for each word

Multiply Results

Multiply the anagram counts from all words together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_LEN 1000

long long factorial(int n) {
    if (n <= 1) return 1;
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % MOD;
    }
    return result;
}

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

long long modInverse(long long a, long long mod) {
    return modPow(a, mod - 2, mod);
}

int solution(char* s) {
    char words[100][MAX_LEN];
    int wordCount = 0;
    int wordLen = 0;
    
    // Split string into words
    for (int i = 0; s[i]; i++) {
        if (s[i] == ' ') {
            words[wordCount][wordLen] = '\0';
            wordCount++;
            wordLen = 0;
        } else {
            words[wordCount][wordLen++] = s[i];
        }
    }
    words[wordCount][wordLen] = '\0';
    wordCount++;
    
    long long result = 1;
    
    for (int i = 0; i < wordCount; i++) {
        int n = strlen(words[i]);
        int freq[256] = {0}; // ASCII frequency array
        
        // Count character frequencies
        for (int j = 0; j < n; j++) {
            freq[(unsigned char)words[i][j]]++;
        }
        
        // Calculate n!
        long long numerator = factorial(n);
        
        // Calculate product of factorials of frequencies
        long long denominator = 1;
        for (int j = 0; j < 256; j++) {
            if (freq[j] > 0) {
                denominator = (denominator * factorial(freq[j])) % MOD;
            }
        }
        
        // Calculate n! / (freq1! × freq2! × ...)
        long long wordAnagrams = (numerator * modInverse(denominator, MOD)) % MOD;
        result = (result * wordAnagrams) % MOD;
    }
    
    return result;
}

int main() {
    char s[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

For k words with average length n, counting frequencies takes O(n) per word

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counts and factorial calculation

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler