4 · Group Anagrams

In an Xcode test target:

import Testing

struct GroupAnagramsTests {

    @Test(arguments: [
        (["stone", "notes", "lemon", "tones", "melon", "apple"], [["apple"], ["lemon", "melon"], ["notes", "stone", "tones"]]),
        ([""], [[""]]),
        (["x", "y", "x"], [["x", "x"], ["y"]]),
    ])
    func groupsWordsMadeOfTheSameLetters(words: [String], expected: [[String]]) {
        #expect(normalised(groupAnagrams(words)) == expected)
    }

    // MARK: - Privates
    private func groupAnagrams(_ words: [String]) -> [[String]] {
        []
    }

    /// Group order and word order inside a group are free, so compare a sorted copy.
    private func normalised(_ groups: [[String]]) -> [[String]] {
        groups
            .map { $0.sorted() }
            .sorted { $0.lexicographicallyPrecedes($1) }
    }
}

In a playground:

func groupAnagrams(_ words: [String]) -> [[String]] {
    [] // your solution
}

/// Group order and word order inside a group are free, so compare a sorted copy.
func normalised(_ groups: [[String]]) -> [[String]] {
    groups
        .map { $0.sorted() }
        .sorted { $0.lexicographicallyPrecedes($1) }
}

let cases: [([String], [[String]])] = [
    (["stone", "notes", "lemon", "tones", "melon", "apple"], [["apple"], ["lemon", "melon"], ["notes", "stone", "tones"]]),
    ([""], [[""]]),
    (["x", "y", "x"], [["x", "x"], ["y"]]),
]
for (words, expected) in cases {
    let got = normalised(groupAnagrams(words))
    print(got == expected ? "PASS" : "FAIL", words, "→", got, "expected", expected)
}

Hash map, used for grouping. The cue is "gather together the ones that…" — that is "group by", and "group by" is a dictionary from a key to a list. The whole problem is choosing the key: something every anagram of a word shares and no non-anagram does.

Two keys work. The word's letters sorted ("stone" → "enost"), or a count of each letter ([1, 0, 0, …], 26 slots). Both are identical across anagrams and differ otherwise.

For each word, compute its key by sorting its letters. Use the key to file the word into a dictionary: key on one side, the list of words that produced it on the other. When every word is filed, the dictionary's lists are the answer.

Time O(n · k log k), for n words of length up to k: each word is sorted once. The letter-count key makes that O(n · k), which matters only when words are long — with k ≤ 100 the sort is fine, and it is the version you'll write correctly under pressure. Space O(n · k) for the keys and the grouped copies of the words.

func groupAnagrams(_ words: [String]) -> [[String]] {
    let groups = Dictionary(grouping: words) { String($0.sorted()) }
    return Array(groups.values)
}

Dictionary(grouping:by:) is the standard library's group-by: it builds [Key: [Element]] in one pass and keeps each group in input order. Writing the loop by hand — groups[key, default: []].append(word) — is equally good; know both, because an interviewer may ask what the one-liner does underneath.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above plus five more — an empty list, repeated words (["ab", "ba", "ab", "abc"]), same letters in different counts ("aab" vs "abb", not anagrams), mixed case ("Tea" vs "eat", not anagrams as written), and "café" spelled with a precomposed é against one spelled with e + combining accent (anagrams, because Swift compares Characters by canonical equivalence) — and 1,000 random word lists, each checked that every word lands in exactly one group, every group shares one sorted key, and no two groups share a key.

["stone", "notes", "lemon", "tones", "melon", "apple"]

The values are the three groups.

[""] — "".sorted() is an empty array, String([]) is "", so the key is the empty string and the result is [[""]]. No special case needed; say that you checked.

Dictionary order changes every run. Swift seeds its hash function randomly per process (SE-0206), so groups.values comes back in a different order each time you run the tests. Compare the result directly against [["notes", "stone", "tones"], …] and the test passes on one run and fails on the next — a flaky test you wrote yourself. The fix is to normalise before comparing (sort each group, then sort the groups), which is what the Xcode stub does. Mentioning this before the interviewer sees it fail is a strong signal.

Smaller one: word.sorted() returns [Character], not a String. Using the array as the key works ([Character] is Hashable), but wrap it in String(...) so the key prints readably when you debug.

• "Can you avoid the sort?" → Count letters into a 26-slot [Int] and use the array as the key; [Int] is Hashable, a tuple would not be. O(n · k). Only valid while the alphabet is fixed and small.
• "What about Unicode, or uppercase?" → Decide what "same letter" means first: lowercase (and fold diacritics if the product wants é = e) before building the key. The sorted-Character key keeps working; the 26-slot array doesn't.
• "Return only the groups with more than one word." → Filter the values: groups.values.filter { $0.count > 1 }. Same cost.