Grouping and Matching with Hash Maps

EditorialUpdated Oct 25, 2026

When equal means the same shape

Group Anagrams: put the words ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'] into groups of anagrams. The answer is [eat, tea, ate], [tan, nat], [bat].

Comparing every pair of words with the anagram check from Frequency Counting with Hash Maps works, but it's O(n²) checks. Here's the better question: what could you compute from a word, on its own, that comes out the same for every word in its group and different for every other? Sort its letters: eat → aet, tea → aet, tan → ant, ate → aet. Anagrams sort to the same letters, and nothing else does.

That value is a key. File every word in a hash map under its key, and the buckets are the groups, in one pass.

Group Anagrams on eat, tea, tan, ate, nat, bat. Each word is shown with its key, its letters sorted: eat gives aet, tea gives aet, tan gives ant, ate gives aet, nat gives ant, bat gives abt. Arrows lead each key to one bucket of a hash map, so the buckets hold eat, tea, ate; tan, nat; bat.

Group Anagrams with a sorted key

The template: compute the key, append the word to its key's list, and return the lists.

vector<vector<string>> groupAnagrams(const vector<string>& strs) {
    unordered_map<string, vector<string>> groups;      // key -> the words that share it
    for (const string& w : strs) {
        string key = w;
        sort(key.begin(), key.end());                  // anagrams sort to the same letters
        groups[key].push_back(w);
    }
    vector<vector<string>> out;
    for (auto& [key, words] : groups) out.push_back(words);
    return out;
}

from collections import defaultdict


def group_anagrams(strs):
    groups = defaultdict(list)                  # key -> the words that share it
    for w in strs:
        key = "".join(sorted(w))                # anagrams sort to the same letters
        groups[key].append(w)
    return list(groups.values())

static List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();   // key -> the words that share it
    for (String w : strs) {
        char[] letters = w.toCharArray();
        Arrays.sort(letters);                              // anagrams sort to the same letters
        groups.computeIfAbsent(new String(letters), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

function groupAnagrams(strs) {
    const groups = new Map();                          // key -> the words that share it
    for (const w of strs) {
        const key = [...w].sort().join('');            // anagrams sort to the same letters
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(w);
    }
    return [...groups.values()];
}

With n words of length up to k, sorting each word costs O(k log k), so it's O(n · k log k) in all, and O(n · k) memory for the map.

A key without sorting. The letter counts are also equal exactly for anagrams, and they take O(k) to compute. In Python a tuple of the 26 counts works as a key:

from collections import defaultdict


def group_anagrams(strs):
    groups = defaultdict(list)
    for w in strs:
        counts = [0] * 26
        for c in w:
            counts[ord(c) - ord('a')] += 1
        groups[tuple(counts)].append(w)         # a tuple of 26 counts: O(k) per word, no sorting
    return list(groups.values())

It groups ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'] the same way. In Java or C++ you'd turn the counts into a string, and then the separators matter (see the second mistake below).

Choose the key

A key has one job: be equal exactly when the items belong together. There are two ways to miss:

Too coarse: two items that don't belong together get the same key, and share a bucket.
Too fine: two items that belong together get different keys, and are split up.

Try it. Each colour below is one group the task wants. Pick the key every word is filed under, and watch the hash map it builds: a bucket mixing colours is too coarse, and a colour in two buckets is too fine. Then switch to same pattern, where a different key is the right one.

The Key Picker: choose the key each word is filed under, and see the hash map it builds

For anagrams both sorted letters and letter counts are right; distinct letters is too coarse (eat and teat share {a,e,t}); the word itself is too fine. For same pattern, only the letter pattern works: each letter renamed a, b, c in the order it first appears, so egg and add are both abb.

Matching one to one

Isomorphic Strings: can the letters of s be replaced to get t, where each letter always maps to the same letter and no two letters map to the same one? "egg" and "add" can (e → a, g → d); "foo" and "bar" can't (o would have to be both a and r).

A map from s's letters to t's checks the first rule: each letter keeps one image. It doesn't check the second. "ab" and "cc" map a → c and b → c, and one map sees nothing wrong. So keep a second map going the other way, and check both. (Comparing the two strings' letter patterns, the key from above, is the same test.)

bool isIsomorphic(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    unordered_map<char, char> sToT, tToS;              // both directions, so the mapping is one-to-one
    for (size_t i = 0; i < s.size(); i++) {
        char a = s[i], b = t[i];
        if ((sToT.count(a) && sToT[a] != b) || (tToS.count(b) && tToS[b] != a))
            return false;                              // a already maps elsewhere, or b is already taken
        sToT[a] = b;
        tToS[b] = a;
    }
    return true;
}

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    s_to_t, t_to_s = {}, {}                     # both directions, so the mapping is one-to-one
    for a, b in zip(s, t):
        if s_to_t.get(a, b) != b or t_to_s.get(b, a) != a:
            return False                        # a already maps elsewhere, or b is already taken
        s_to_t[a], t_to_s[b] = b, a
    return True

static boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Character> sToT = new HashMap<>(), tToS = new HashMap<>();   // both directions
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        if (sToT.getOrDefault(a, b) != b || tToS.getOrDefault(b, a) != a)
            return false;                              // a already maps elsewhere, or b is already taken
        sToT.put(a, b);
        tToS.put(b, a);
    }
    return true;
}

function isIsomorphic(s, t) {
    if (s.length !== t.length) return false;
    const sToT = new Map(), tToS = new Map();          // both directions, so the mapping is one-to-one
    for (let i = 0; i < s.length; i++) {
        const a = s[i], b = t[i];
        if ((sToT.has(a) && sToT.get(a) !== b) || (tToS.has(b) && tToS.get(b) !== a))
            return false;                              // a already maps elsewhere, or b is already taken
        sToT.set(a, b);
        tToS.set(b, a);
    }
    return true;
}

Each prints true, false, true, false and false for "egg" and "add", "foo" and "bar", "paper" and "title", "ab" and "cc", and "badc" and "baba". O(n) time, and O(1) space for a fixed alphabet.

Word Pattern is the same with words: each letter of pattern maps to one word of s and back. One more check comes first, the lengths:

def word_pattern(pattern, s):
    words = s.split()
    if len(words) != len(pattern):
        return False                            # zip would stop at the shorter one and hide the mismatch
    letter_to_word, word_to_letter = {}, {}
    for c, w in zip(pattern, words):
        if letter_to_word.get(c, w) != w or word_to_letter.get(w, c) != c:
            return False
        letter_to_word[c], word_to_letter[w] = w, c
    return True

It prints True, False, False, False and False for "abba" with "dog cat cat dog", "abba" with "dog cat cat fish", "aaaa" with "dog cat cat dog", "abba" with "dog dog dog dog", and "aaaa" with "dog dog dog".

When a key can't work

Keys group things that are "the same" in some sense. Look for "group", "same letters", "same pattern", "maps to", "one-to-one", and ask what one value you could compute per item that decides the group. Some keys worth knowing:

anagrams: the sorted letters, or the 26 counts;
the same letter pattern: each letter renamed in order of first appearance;
the same shape up to a shift (abc, bcd, xyz): the gaps between neighbouring letters, mod 26;
points on the same line through the origin: the slope as a reduced fraction.

And the limit. Two items share a bucket exactly when their keys are equal, and equality is transitive: if a = b and b = c, then a = c. So a key can only capture a relation that's transitive too. "Differs by one letter" isn't (cat ~ cot ~ cog, but cat and cog differ in two), so no key groups words that way. That kind of problem is a graph, like Word Ladder.

Common mistakes

One map for a one-to-one match. Only s_to_t

"ab" and "cc" gives True: a and b both map to c, and nothing checks that c is taken. (Swapped, "cc" and "ab" gives False, so the bug depends on the order of the arguments.) Keep the reverse map too.

A counts key without separators. "".join(map(str, counts))

['abbbbbbbbbbb', 'aaaaaaaaaaab'] comes back as one group, [['abbbbbbbbbbb', 'aaaaaaaaaaab']]. "abbbbbbbbbbb" has counts 1 and 11, "aaaaaaaaaaab" has 11 and 1, and both join to "111" followed by 24 zeros. Use a tuple, or join with a separator such as #: then the two words land in 2 groups.

A list as a key in Python. key = sorted(w)

It crashes with TypeError: unhashable type: 'list': sorted returns a list, and lists can change, so they can't be keys. Join it into a string or make it a tuple.

Skipping the length check in Word Pattern. zip(pattern, words) on its own

"aaaa" with "dog dog dog" gives True. zip stops at the shorter of the two, so the fourth a is never checked. Compare the lengths first.

Check yourself

Quiz

1 / 5

Multiple choice

Which key groups anagrams correctly?

Practice problems

From easier to harder:

Isomorphic Strings: two maps, one each way.
Word Pattern: the same with words, after a length check.
Group Anagrams: a key per word, a list per key.

Then the Hashing Quiz checks the whole section.