The Character Clans

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3
Asked in
iHeartMedia

Problem

Given a list of strings, group strings that have the same set of distinct characters (not the same multiset). Return a list of groups, where groups are ordered by the first appearance of any member, and within each group members appear in input order.

Words sharing the same letters belong to the same clan.

Example

Input:

words = ["eat","tea","ate","bat","tab","abc"]

Output:

[["eat","tea","ate"],["bat","tab"],["abc"]]

Worked solution and explanation

Why this problem exists in real interviews

Grouping words by their unique character set tests frozenset as a dict key and whether you can normalize words to their distinct character signature for grouping.

Break down the requirements

Step 1: Compute the character set for each word

Convert each word to a frozenset of its characters. This normalizes 'abc' and 'cba' to the same key.

Step 2: Group words by their character set

Use the frozenset as a dict key and accumulate words sharing the same set.

Step 3: Return the groups as a list of lists

Extract the values from the grouping dict.

The solution

Frozenset-keyed grouping by character signature
def group_by_chars(words):
    groups = {}
    for word in words:
        key = frozenset(word)
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    result = []
    for key in groups:
        result.append(groups[key])
    return result

Common follow-up questions