Practice › Hashing & Two Pointers
Group Anagrams Count
Medium · Hashing & Two Pointers · Asked at Amazon, Google, Microsoft, Uber
Group the words so that anagrams are in the same group. Print the number of groups.
Input
First line: n. Second line: n words (lowercase) separated by spaces.
Output
The number of anagram groups.
Constraints
- 1 ≤ n ≤ 10^4
- 1 ≤ word length ≤ 100
Use the sorted word (or a 26-letter count) as a hash map key.
Example 1
Input
6 eat tea tan ate nat bat
Output
3
Example 2
Input
1 a
Output
1
Hints
- Two words are anagrams exactly when their sorted letters are the same.
- Use the sorted word as a key in a hash set; the number of distinct keys is the number of groups.
Approach
Sort the letters of each word to get its canonical form ("eat", "tea" and "ate" all become "aet"). Insert the forms into a hash set; its size is the number of groups. For long words, a 26-letter count string makes the key in O(L) instead of O(L log L).
Complexity: O(n · L log L) time · O(n · L) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<string> groups;
for (int i = 0; i < n; i++) {
string w;
cin >> w;
sort(w.begin(), w.end());
groups.insert(w);
}
cout << groups.size() << "\n";
return 0;
}Python solution
n = int(input())
words = input().split()
print(len({"".join(sorted(w)) for w in words[:n]}))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<String> groups = new HashSet<>();
for (int i = 0; i < n; i++) {
char[] w = sc.next().toCharArray();
Arrays.sort(w);
groups.add(new String(w));
}
System.out.println(groups.size());
}
}