Group tile racks that hold the same letters

Arrays, strings and hash maps Mid-level Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
racks = ["tan", "nat", "ant", "bat"]
g: dict[str, list[str]] = {}
for r in racks:
    g.setdefault("".join(sorted(r)), []).append(r)
print(len(g), g["ant"])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2 ['tan', 'nat', 'ant']

Right: three racks share the sorted key 'ant'; 'bat' makes the second group.

The sorted string is an order-free key, so the dict ends with two keys and appends keep arrival order.

Why not the others?
  • B 4 ['ant']. That would happen only if the key kept the original order of letters.
  • C 2 ['ant', 'nat', 'tan']. Groups keep the order racks arrive in; nothing sorts the words inside a group.

30-second answer

Turn each rack into a key that ignores order, then group by that key in a dict. A 26-slot letter count costs O(k) per rack of length k, so the whole job is O(n·k); sorting each rack as the key costs O(n·k log k). The groups and keys take O(n·k) space. Dicts keep insertion order, which gives the required group order for free.

Practise saying it · 45 s. No recording, just a timer

Explain your grouping key and why it is correct.

Say your answer out loud, then check which of these points you covered:

  • Order-free key
  • Counts or sorted string, with costs
  • Dict keeps first-appearance order

Deep dive

Two racks belong together exactly when their letter counts match, so the count tuple is a perfect key: equal racks get equal keys, different racks never share one.

Tuples are hashable; lists are not, which is why the counts are converted with tuple(...).

Sorted strings make a shorter, readable key and are fine when racks are short; counts win when racks are long or the alphabet is small.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def group_racks(racks: list[str]) -> list[list[str]]:
    groups: dict[tuple[int, ...], list[str]] = {}
    for word in racks:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - ord("a")] += 1
        groups.setdefault(tuple(counts), []).append(word)
    return list(groups.values())

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun groupRacks(racks: List<String>): List<List<String>> {
    val groups = LinkedHashMap<String, MutableList<String>>()
    for (word in racks) {
        val counts = IntArray(26)
        for (ch in word) counts[ch - 'a']++
        val key = counts.joinToString(",")
        groups.getOrPut(key) { mutableListOf() }.add(word)
    }
    return groups.values.toList()
}

Common mistakes

  • Using a set of letters as the key, which merges 'aab' with 'ab'.
  • Sorting the output groups or words when the question asks for first-appearance order.

Senior take & follow-ups

State the key choice and its cost per item. Being explicit that equal keys mean equal multisets is what makes the answer convincing.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if racks can hold any Unicode letter?

    Show hint

    Use collections.Counter frozen to a sorted tuple of items, or the sorted string; a 26-slot array no longer fits.

  2. How would you stream racks from a file?

    Show hint

    Keep only the dict of key to group; each rack is processed once.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.