71. Group Anagrams Together

Given n words, group the ones that are anagrams of each other. Print the groups in the order each group's first word first appeared, each group's words space-separated in their original relative order, and groups separated by ' | '.

Input: The first line contains an integer n. Each of the next n lines contains one word. Output: Print the anagram groups, each group's words space-separated in original order, groups separated by ' | ', ordered by first appearance.

1 <= n <= 1000, 1 <= word length <= 100

Preserving BOTH each group's internal word order AND the groups' own first-appearance order requires care - a plain hashmap naturally preserves insertion order for each key's list, but you must track the ORDER OF KEYS separately (e.g. with an ordered map or a separate list of first-seen keys) to get the groups themselves in the right order.

Given a list of words, group together every set of words that are anagrams of each other (contain exactly the same letters, just rearranged). Brute force: Compare every pair of words directly (checking if their sorted letters match) to decide grouping - this costs O(n² * L log L) where L is word length, unnecessary when a hashmap keyed by sorted letters groups everything in one pass. Optimised: Using the SORTED version of each word as a hashmap key means every anagram of a given word automatically maps to the exact same key - a single pass building this hashmap groups all anagrams together in O(n * L log L) total, with no pairwise comparisons needed at all.

Instead of sorting each word, build its canonical key by counting occurrences of each of the 26 lowercase letters into a fixed-size array and turning those counts into a key (for example a delimited string of counts). Two words are anagrams exactly when their frequency arrays match exactly, and computing that frequency array is a single linear pass over the word. This drops the per-word cost from O(L log L) down to O(L), which matters when words get long. Time: O(n*L) Space: O(n*L)

For each word, sort its own characters to produce a canonical form; two words are anagrams exactly when their sorted forms are identical. Use that sorted string as a hash map key and append each word to the list for its key in the order it's encountered, then output the groups in the order each key was first seen. This collapses anagram words into the same bucket with no pairwise comparisons at all, at the cost of an O(L log L) sort per word. Time: O(n * L log L) Space: O(n*L)

For each word, compare it against every other not-yet-grouped word by checking whether the two share identical character counts (i.e., are anagrams of each other), merging matching words into the same group as they're discovered. This works because anagram-ness is checked directly and exhaustively, but it repeats an O(word length) comparison against every remaining word for every word. Time: O(n^2 * L) Space: O(n*L)

1. For every word, sort its letters alphabetically - this sorted form is identical for all anagrams of that word (this becomes a grouping 'key'). 2. Use a hashmap from this sorted-letters key to a list of original words sharing that key, appending each word in the order it appears. 3. Print the groups in the order each group's key was FIRST encountered, preserving each group's internal word order.

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 hashmap storing every word grouped by its sorted-letter key.

A word with no anagram partners, forming its own singleton group; all n words being anagrams of each other (a single group); n up to 1000 and word length up to 100 for performance.

Be ready to mention the alternative key (a fixed-size character-count array, like 26 counts for lowercase letters, 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 mention if pushed further.