Arrays and Hashing
Grouping by a canonical key
Design a key so that everything which belongs together produces the same key, and nothing else does.
Key idea
Canonical form
A canonical form is a rewriting rule that maps everything in a group to one identical representative, and keeps different groups apart. Once you have one, grouping is a single pass: compute the key, append to that key's bucket.
Take a concrete case: group numbers that use the same digits. 123, 231, and 312 belong together. A canonical form for that is the digits in sorted order, so all three become "123".
The grouping loop itself is three lines and is always the same. Choosing the key is the entire problem.
Keys do not have to be strings
Any hashable value works, and a tuple is the usual choice when the signature is naturally several numbers. Here the canonical form of a word is its shape: which positions repeat, ignoring the actual letters. "noon" and "baab" have the same shape.
Gotcha
The list is not hashable
Returning shape as a list and using it as a key raises TypeError: unhashable type: 'list'. The fix is tuple(shape), the same values in an immutable container.
This is not a Python quirk to memorize around. A dict key has to have a stable hash, and a list's contents can change after insertion, which would strand the entry in the wrong bucket forever.
Why it works
The test for a good key
Two things must be true, and it is worth checking both explicitly before you write the loop. Everything that belongs in one group produces the same key. Nothing outside that group produces it.
Failing the first splits a group in two. Failing the second merges groups that should be separate. A key built from a sum almost always fails the second test, because different collections routinely add up to the same number.
defaultdict versus the alternatives
Three ways to append into a bucket that might not exist yet. They behave identically here, and the first is the one to write.
Gotcha
One caution about defaultdict
Because reading a missing key inserts it, a later membership test can be surprised by keys you never meant to create. If you build a defaultdict and then ask whether some key is present, you may have created it yourself by asking earlier.
Inside a tight grouping loop this never matters. It starts mattering when the same dict is used for grouping and then queried elsewhere, which is a good reason to convert with dict(groups) once the building is finished.
Pick the canonical key
You want to group points with positive coordinates that lie on the same line through the origin. Which key is a correct canonical form?
Design the key
Two grouping problems where the only real work is picking the key. group_by_length buckets words by their length. group_shifted is harder: group strings that are the same sequence of gaps between consecutive letters, so "abc" and "xyz" belong together, and so do "az" and "ba" because the gap wraps around 26.
Tests
print(group_by_length(["a", "bb", "cc", "ddd"])) print(group_shifted(["abc", "bcd", "xyz", "az", "ba", "a", "z"]))
Output
Run the tests when you are ready.
Group Anagrams
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.