21. Group Similar Intents

Problem

Fin's conversational log pipeline batches normalized customer query strings before routing them to intent classification. As a cheap pre-clustering signal, queries that are anagrams of each other (same multiset of characters) get grouped together so the downstream intent bucketer can treat them as one candidate cluster before doing any real semantic comparison work.

Given a list of query strings, group the anagrams together. Each group must preserve the original relative order of its members, and the groups themselves must be ordered by the original index of their first member, ascending.

Source: src/21_group_similar_intents.py

def group_by_signature(queries: list[str]) -> list[list[str]]:
    ...

>>> group_by_signature(["eat", "tea", "tan", "ate", "nat", "bat"])
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

>>> group_by_signature([])
[]

>>> group_by_signature(["abc", "abc"])
[["abc", "abc"]]

Step-by-Step Approach

1. Two strings are anagrams exactly when they share the same multiset of characters, so any canonical form of that multiset works as a grouping key.
2. The cheapest canonical form to compute is the sorted-character string: sort each query's characters and join them back into a string.
3. Use a dict keyed by that sorted signature. For each query in input order, compute its signature and append the query to groups[signature], creating the list on first sight.
4. Because Python dicts preserve insertion order, and a signature is first inserted at the index of the first query that produces it, iterating groups.values() at the end yields groups already ordered by their first member's original index — no separate sort needed.
5. Within each group, queries were appended in the order they were encountered, so relative order is preserved automatically.
6. Return list(groups.values()).

The key insight is that "group by some derived property" collapses to "hash map keyed by a canonical signature," and relying on Python's insertion-ordered dict sidesteps any extra bookkeeping for output order.

Reference solution

def group_by_signature(queries: list[str]) -> list[list[str]]:
    # dict preserves first-insertion order, which is exactly first-member-index order; O(n*k log k)
    groups: dict[str, list[str]] = {}
    for query in queries:
        # sorted chars joined back to a hashable str key
        signature = "".join(sorted(query))
        # create list on first sight, else reuse
        groups.setdefault(signature, []).append(query)
    # insertion order == first-member-index order
    return list(groups.values())

Key Functions & Tricks

• sorted(query) — canonical signature: anagrams share the same sorted character list.
• "".join(sorted(query)) — turns the sorted char list into a hashable string dict key.
• dict.setdefault(key, []) — get-or-create the group's list in one expression.
• dict.values() — insertion-ordered (3.7+), so no separate sort by first-index needed.
• list(groups.values()) — materializes the values view into a concrete list.

How to Recognize This Pattern