Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Two words are anagrams exactly when their sorted letters are the same.
  2. 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());
    }
}

Solve Group Anagrams Count online · All practice problems