A spelling-bee coach has n words (duplicates allowed). Group the words that are anagrams of each other (same letters, same counts).
Print one group per line. Inside a group, sort the words alphabetically (keep duplicates). Sort the groups by their first word.
Constraints
- 1 ≤ n ≤ 10000
- each word has 1–20 lowercase letters
Input and output
- Input
- Line 1: n. Line 2: n lowercase words.
- Output
- One line per group, words separated by spaces.
Examples
Input 1
6
rat tar art star tars cheeseOutput
art rat tar
cheese
star tarsrat, tar and art share the letters a, r, t; star and tars share a, r, s, t; cheese is alone.
Input 2
2
abc cabOutput
abc cabBoth are anagrams of each other.
Show hints
- Two words are anagrams exactly when their sorted letters match.
- Use that sorted form as a key in a hash map.
Show the explanation
Sorting the letters of a word gives a signature that every anagram shares (tar and art both become art). Put each word into a hash map under its signature, then sort each group and sort the groups by their first word for a stable output. Cost: O(n · k log k) for words of length k.
Original UniCircle question. Last reviewed 22 Oct 2026.