Minimum Unique Word Abbreviation

Minimum Unique Word Abbreviation

What is this problem about?

The Minimum Unique Word Abbreviation problem gives you a target word and a list of dictionary words. An abbreviation replaces any subset of characters in a word with a count. Find the shortest abbreviation of the target that doesn't match any dictionary word (with the fewest remaining letters). This hard Minimum Unique Word Abbreviation coding problem combines backtracking, bit manipulation, and string compression.

Why is this asked in interviews?

Amazon and Google ask this hard problem because it requires modeling abbreviation as a bitmask over the kept characters, then verifying uniqueness against all dictionary words. The array, backtracking, string, and bit manipulation interview pattern is fully exercised. It tests the ability to enumerate all abbreviation forms efficiently using bitmasks over a fixed-length word.

Algorithmic pattern used

Bitmask enumeration + string conflict checking. For a word of length n, there are 2^n possible abbreviations (each bit determines whether the character is kept or abbreviated). For each bitmask, compute the abbreviation length (number of "kept" characters + number of numeric segments). Use bitmask conflict checking: precompute a conflict mask for each dictionary word against the target — a dictionary word conflicts if it "matches" a given abbreviation bitmask. Enumerate bitmasks from fewest kept characters upward; return the first non-conflicting one.

Example explanation

Target: "word", dictionary: ["wood", "wore"].

• Abbreviation "4" (all abbreviated): conflicts with both dictionary words? Check.
• "w3" (keep 'w'): does "wood" match? 'w' + 3 chars = "wood" (4 chars). Conflicts.
• "wo2" (keep 'w','o'): does "wood" match? wo+2=wood? Yes. Conflicts. Continue until finding abbreviation that doesn't conflict with any dictionary word.

Common mistakes candidates make

• Generating abbreviations as strings before checking conflicts (slow).
• Not precomputing conflict masks for dictionary words.
• Abbreviation length computation errors (adjacent abbreviated characters merge into one number).
• Enumerating bitmasks in the wrong order (should go from fewest kept characters first).

Interview preparation tip

Problems involving "subset of characters to keep/mask" naturally map to bitmasks. When a word has ≤ 20 characters, enumerate all 2^n bitmasks and check each condition in O(1) using precomputed masks. The tricky part here is the abbreviation length formula: count contiguous runs of 0-bits (abbreviated sections) and count 1-bits (kept characters). Practice building abbreviations from bitmasks step by step on paper before coding, as the index arithmetic is easy to get wrong under pressure.