LeetCode 2514: Count Anagrams
Problem Description
Explanation:
To solve this problem, we can follow these steps:
- Split the input string
sinto individual words. - For each word in
s, sort the characters to get a canonical representation of the word. - Count the frequency of each canonical word.
- Calculate the number of distinct anagrams by multiplying the factorial of the counts of each canonical word.
- Return the result modulo 10^9 + 7.
Time Complexity:
The time complexity of this approach is O(n * k * log(k)), where n is the number of words in the input string s and k is the average length of each word.
Space Complexity: The space complexity is O(n * k) to store the canonical representation of each word.
:
Solutions
class Solution {
public int countAnagrams(String s) {
final int MOD = 1000000007;
String[] words = s.split(" ");
Map<String, Integer> wordCounts = new HashMap<>();
for (String word : words) {
char[] chars = word.toCharArray();
Arrays.sort(chars);
String canonical = new String(chars);
wordCounts.put(canonical, wordCounts.getOrDefault(canonical, 0) + 1);
}
long result = 1;
for (int count : wordCounts.values()) {
result = (result * factorial(count)) % MOD;
}
return (int) result;
}
private long factorial(int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result = (result * i) % 1000000007;
}
return result;
}
}Loading editor...