{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Group Anagrams – Solution & Complexity

Interview solutions
/
Group Anagrams

Solution Walkthrough

  1. Step 1: Understand the brute-force baseline

    • Compare every word with every other word and check whether their letter counts match.
    • That works, but pairwise comparison becomes too slow once many strings are present.

  2. Step 2: Choose the optimal key

    • Anagrams share the same 26 lowercase letter frequencies.
    • Turn that frequency table into a hashable key, then bucket words by key in one scan.

  3. Step 3: Keep the output deterministic

    • The live judge compares exact JSON, so avoid returning groups in arbitrary hash-map order.
    • Record each key the first time it appears, then emit groups in that recorded order.

  4. Step 4: Final solution (all languages)

    A frequency-signature hash map groups words in linear time while preserving first-seen order.

    def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[tuple[int, ...], list[str]] = {}
    order: list[tuple[int, ...]] = []

    for word in strs:
        counts = [0] * 26
        for char in word:
            counts[ord(char) - ord("a")] += 1
        key = tuple(counts)
        if key not in groups:
            groups[key] = []
            order.append(key)
        groups[key].append(word)

    return [groups[key] for key in order]

  5. Step 5: Complexity summary

    • Time: O(n * k) because each character is counted once.
    • Space: O(n * k) for the stored groups and generated keys.

FAQ

See also

Practice Group Anagrams online (run code in the browser)3Sum solution (medium)Contains Duplicate solution (easy)Find All Anagrams in a String solution (medium)First Unique Character in a String solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?