Count Anagrams - Video Solutions

Problem Overview: You receive a sentence containing multiple words separated by spaces. For each word, count how many distinct anagrams can be formed using its characters, then multiply the counts across all words. Because characters may repeat, the number of valid permutations must account for duplicate letters and the result is returned modulo 1e9+7.

Approach 1: Factorial Counting with Frequency Map (O(n) time, O(n) space)

This approach treats each word independently and uses classic combinatorics for permutations with duplicates. For a word of length k, the number of unique permutations is k! / (freq[c1]! * freq[c2]! ...), where freq is the count of each character. You compute character frequencies using a hash table, then evaluate the formula using precomputed factorials and modular inverses under modulo 1e9+7. Precomputing factorials up to the total string length allows constant-time factorial lookups. Multiply the result for each word to obtain the final answer. Time complexity is O(n) where n is the sentence length, and space complexity is O(n) for factorial tables.

The key insight: repeated characters reduce the total permutations. Using modular inverse avoids division under modulo arithmetic. This is a direct application of combinatorics and modular math, and it scales easily for long strings because factorial values are reused.

Approach 2: Dynamic Programming on Permutation Construction (O(k * alphabet) per word, O(k) space)

This method builds permutations incrementally. For each word, you track how many characters of each type have been placed and compute the number of ways to build permutations step by step. A DP state represents how many characters have been used so far, and transitions add another character while respecting its frequency limit. The transition count reflects how many positions the new character can occupy relative to previously placed characters. This technique avoids direct factorial formulas and instead derives counts through iterative state updates.

Although conceptually useful for understanding permutation counting, the DP approach is slower and more complex to implement. Each word requires iterating through its characters and updating states based on remaining frequencies. Time complexity depends on word length and alphabet size, typically around O(k * 26) per word with O(k) space.

Recommended for interviews: The factorial counting approach is the expected solution. It demonstrates knowledge of permutation formulas, modular arithmetic, and efficient preprocessing. Interviewers want to see you recognize the formula for permutations with duplicates and implement factorial + modular inverse correctly. The DP approach is rarely required but shows deeper understanding of permutation construction.