Word Abbreviation - Solution & Explanation

Problem Overview: Given a list of distinct words, generate the shortest possible abbreviation for each word such that no two abbreviations collide. An abbreviation keeps the first letter, last letter, and replaces the middle characters with their count. If multiple words produce the same abbreviation, you must increase the prefix length until every abbreviation becomes unique.

Approach 1: Pairwise Prefix Expansion (Brute Force) (Time: O(n² * L), Space: O(n))

Start by generating the default abbreviation for every word using prefix length 1. Then compare every pair of words. When two abbreviations collide, increase the prefix length for both words and recompute their abbreviations. This process continues until all conflicts disappear. The key operation is repeatedly checking pairs and rebuilding abbreviations, which becomes expensive for large inputs. This approach is straightforward and demonstrates the rule behind abbreviation conflicts but scales poorly because every conflict may trigger multiple recomputations.

Approach 2: Sorting + Longest Common Prefix (Time: O(n log n * L), Space: O(n))

Sort words by their potential abbreviation group: same first letter, last letter, and length. Within each group, only nearby words in sorted order can collide. Compute the longest common prefix between adjacent words to determine the minimum prefix required to differentiate them. This reduces unnecessary comparisons across unrelated words. Sorting clusters similar words together, and prefix comparison determines how many characters must remain uncompressed. This approach improves performance significantly and uses standard sorting and string operations.

Approach 3: Grouped Trie (Optimal) (Time: O(n * L), Space: O(n * L))

Group words by (length, first character, last character) because only these can produce identical abbreviations. For each group, build a Trie where each node tracks how many words pass through it. While inserting characters, the first node with count 1 identifies the unique prefix length for that word. Once the unique prefix is known, build the abbreviation using that prefix plus the compressed middle count. The Trie efficiently detects the earliest divergence between words, eliminating repeated comparisons. Each character is processed once during insertion and lookup, producing near-linear complexity relative to total characters.

Recommended for interviews: The grouped Trie approach is the expected solution. It demonstrates control over array grouping, Trie design, and greedy prefix selection. Mentioning the brute-force idea shows you understand the conflict rule, but implementing the Trie-based grouping proves you can scale the solution efficiently.