Group Anagrams

Given n lowercase words, group the words such that all words in the same group are anagrams of one another. Order the groups by the index at which the first member of that group first appears in the input, and within each group print the words in the order they originally appeared.

Input: The first line contains a single integer n, the number of words. Each of the next n lines contains one lowercase word. Output: One line per group, listing the group's words separated by single spaces, in the group order described above. The number of output lines equals the number of groups.

1 <= n <= 10^4. 1 <= |word_i| <= 20. Each word consists only of lowercase English letters.

Using an ORDER-PRESERVING map (not a plain hash map, whose iteration order isn't guaranteed) is exactly what lets both the groups' own order AND each group's internal word order come out correctly, matching this problem's specific ordering requirement.

Given a list of words, group together every set of words that are anagrams of each other. Brute force: Compare every pair of words directly (checking if their sorted letters match) to decide grouping - this costs O(n² * L log L), unnecessary when a hash map keyed by sorted letters groups everything in a single pass. Optimised: Using the SORTED version of each word as a hash map key means every anagram of a given word automatically lands under the SAME key - a single pass building this map groups all anagrams together in O(n * L log L) total, with zero pairwise comparisons.

1. For every word, sort its own letters alphabetically - this sorted form is IDENTICAL for all anagrams of that word, making it a natural grouping key. 2. Use an order-preserving map (like a LinkedHashMap) from this sorted-letters key to a list of original words sharing that key. 3. Scan the words once, appending each to the list stored under its key - the map's own insertion order then naturally gives groups ordered by first appearance.

Time: O(n * L log L), where n is the number of words and L is the maximum word length - each word needs its letters sorted once. Space: O(n * L), for the map storing every word grouped by its sorted-letter key.

A word with no anagram partner forms its own group of size one. All n words could be anagrams of each other, producing a single group.

Be ready to mention the alternative key of a fixed-size 26-count array (instead of a sorted string) as a way to avoid the log L sorting cost per word, achieving O(n * L) instead - a nice optimization to bring up if pushed further.