PythonMediumCollections20 min
Group anagrams in first-seen order
Preserve input order inside each group and order groups by their first encountered member. Print a JSON array of arrays using compact separators. Interviewers use this problem to assess hash each word using its fixed-alphabet frequency tuple.
Input
First line: n. Next n lines: one nonempty lowercase word per line.
Output
Print the result on one line; print an empty line for an empty string.
Constraints
0 <= n <= 10000; each word has 1 to 100 characters.
Example
Input
6 eat tea tan ate nat bat
Output
[["eat","tea","ate"],["tan","nat"],["bat"]]
Example 2 input
4 aab aba abb bab
Output
[["aab","aba"],["abb","bab"]]
Different multiplicities create distinct groups.
Public test cases (2)
Input
6 eat tea tan ate nat bat
Expected output
[["eat","tea","ate"],["tan","nat"],["bat"]]
Input
3 a a b
Expected output
[["a","a"],["b"]]
Hints (2)
- Identify the state needed to avoid repeated work.
- Hash each word using its fixed-alphabet frequency tuple.
Target complexity: time O(S + 26n), where S is total characters · space O(S + 26n) including groups