Word Abbreviation

Word Abbreviation

What is this problem about?

In "Word Abbreviation," you are given a list of unique strings and need to generate the shortest unique abbreviation for each word. An abbreviation is formed by keeping the first k characters, then the number of omitted characters, and finally the last character. If an abbreviation is not unique (matches another word's abbreviation) or isn't shorter than the original word, you must increase k to provide more prefix context until it becomes unique.

Why is this asked in interviews?

Meta and Google ask this to evaluate a candidate's proficiency with Tries and String Manipulation. It requires balancing multiple constraints: uniqueness, length, and prefix matching. It tests whether you can manage a group of items that conflict with each other and resolve those conflicts iteratively or recursively.

Algorithmic pattern used

The most efficient approach uses a Trie (Prefix Tree) or Sorting with Grouping. You group words that have the same initial abbreviation (first char + length + last char). For each group, you build a Trie of their prefixes. The point where a word's path in the Trie becomes unique determines the value of k needed for its abbreviation.

Example explanation

Words: ["internal", "interval"].

1. Initial abbreviation: Both are i6l. They conflict!
2. Increase prefix length k.
   • k=2: in5l vs in5l. Still conflict.
   • k=3: int4l vs int4l. Still conflict.
   • k=4: inte3l vs inte3l. Still conflict.
   • k=5: inter2l vs inter2l. Still conflict.
   • k=6: intern1l (length 8, not shorter) and interv1l. Since intern1l is not shorter than internal, we just use the original words.

Common mistakes candidates make

• Infinite Loops: Not having a clear exit condition when the abbreviation length reaches the word length.
• Incorrect Length Calculation: Calculating the number of omitted characters as length - k instead of length - k - 1.
• Global vs Local Uniqueness: Forgetting that an abbreviation must be unique across the entire list, not just within its initial group.

Interview preparation tip

When dealing with prefix-based uniqueness, always consider a Trie. It allows you to count how many words share a certain prefix at any given node, making it easy to find the first "non-shared" node.