Minimum Unique Word Abbreviation solution and explanation
Google
2 more videos on this problem
The problem
A string can be abbreviated by replacing any number of non-adjacent substrings with their lengths. For example, a string such as "substitution" could be abbreviated as (but not limited to):
"s10n"("s ubstitutio n")"sub4u4"("sub stit u tion")"12"("substitution")"su3i1u2on"("su bst i t u ti on")"substitution"(no substrings replaced)
Note that "s55n" ("s ubsti tutio n") is not a valid abbreviation of "substitution" because the replaced substrings are adjacent.
The length of an abbreviation is the number of letters that were not replaced plus the number of substrings that were replaced. For example, the abbreviation "s10n" has a length of 3 (2 letters + 1 substring) and "su3i1u2on" has a length of 9 (6 letters + 3 substrings).
Given a target string target and an array of strings dictionary, return an abbreviation of target with the shortest possible length such that it is not an abbreviation of any string in dictionary. If there are multiple shortest abbreviations, return any of them.
Example 1:
Input: target = "apple", dictionary = ["blade"] Output: "a4" Explanation: The shortest abbreviation of "apple" is "5", but this is also an abbreviation of "blade". The next shortest abbreviations are "a4" and "4e". "4e" is an abbreviation of blade while "a4" is not. Hence, return "a4".
Example 2:
Input: target = "apple", dictionary = ["blade","plain","amber"] Output: "1p3" Explanation: "5" is an abbreviation of both "apple" but also every word in the dictionary. "a4" is an abbreviation of "apple" but also "amber". "4e" is an abbreviation of "apple" but also "blade". "1p3", "2p2", and "3l1" are the next shortest abbreviations of "apple". Since none of them are abbreviations of words in the dictionary, returning any of them is correct.
Constraints:
m == target.lengthn == dictionary.length1 <= m <= 210 <= n <= 10001 <= dictionary[i].length <= 100log2(n) + m <= 21ifn > 0targetanddictionary[i]consist of lowercase English letters.dictionarydoes not containtarget.
Approach overview
Problem Overview: Given a target word and a dictionary, return the shortest possible abbreviation of the target such that no word in the dictionary shares the same abbreviation. Abbreviations replace consecutive characters with their count (for example international → i10l). Only dictionary words with the same length as the target can conflict.
Approach 1: Brute Force Abbreviation Generation (Exponential Time, O(2^n * n) time, O(n) space)
Generate every possible abbreviation of the target using backtracking. For each generated abbreviation, compare it against all dictionary words of the same length and check whether the abbreviation could represent that word. If any dictionary word matches the abbreviation pattern, discard it. Otherwise keep the abbreviation and track the shortest one. This works because a word of length n has 2^n possible abbreviation masks where each bit decides whether a character is kept or abbreviated.
The downside is the validation cost. For each abbreviation you must test it against multiple dictionary entries, which leads to a large search space when n grows. This approach demonstrates the problem mechanics clearly but becomes slow when the target length approaches the upper constraints.
Approach 2: Bitmask + Backtracking with Conflict Masks (Optimal, O(2^n * m) time, O(m) space)
A more efficient strategy encodes character differences between the target and each dictionary word as bitmasks. First filter the dictionary to keep only words with the same length as the target. For every remaining word, compute a mask where bit i is set if the character differs from the target at position i. These masks represent positions that must remain visible to distinguish the words.
Next perform a backtracking search over bitmasks representing which positions in the target remain visible. A candidate mask is valid if it intersects with every dictionary difference mask (meaning at least one distinguishing character remains visible). The abbreviation length can be computed from the mask by counting visible characters and compressed number segments. The search tries masks that minimize this length while pruning branches that cannot beat the current best result.
This approach relies heavily on bit manipulation for fast masking operations and uses array storage for dictionary masks. Bitwise checks allow the algorithm to quickly test whether a candidate abbreviation distinguishes all dictionary words. In practice this reduces unnecessary comparisons and makes the exponential search manageable.
Recommended for interviews: Interviewers expect the bitmask + backtracking approach. Starting with brute force shows you understand abbreviation generation, but the optimized mask strategy demonstrates stronger algorithmic thinking and efficient pruning. The key idea is converting string differences into bitmasks so uniqueness checks become constant-time bit operations.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Abbreviation Generation | O(2^n * n) | O(n) | Good for understanding how abbreviations are formed and validated |
| Bitmask + Backtracking with Conflict Masks | O(2^n * m) | O(m) | Best general solution when dictionary size is moderate |
| Bitmask Search with Pruning | O(2^n) average with pruning | O(m) | Preferred interview solution for minimizing abbreviation length efficiently |
Frequently asked questions
Is Minimum Unique Word Abbreviation easy or hard?
Minimum Unique Word Abbreviation is classified as a Hard problem. It combines string processing, bit manipulation, and exponential search with pruning. Understanding how to convert character differences into bitmasks is the key insight that makes the optimized solution manageable.
Minimum Unique Word Abbreviation Python/Java solution
Python and Java implementations typically represent abbreviation choices as integer bitmasks. The algorithm generates candidate masks using DFS or backtracking, checks conflicts using bitwise operations, and calculates abbreviation length based on visible character positions.
How to solve Minimum Unique Word Abbreviation in O(n)?
An O(n) solution does not exist because the algorithm must explore combinations of abbreviation positions. The practical approach uses bitmask enumeration with pruning, which explores up to 2^n candidate masks but significantly reduces work using conflict masks and early pruning.
What is the best approach for Minimum Unique Word Abbreviation?
The most effective solution uses bitmasking with backtracking. Each dictionary word is converted into a bitmask representing positions where it differs from the target word. During the search, a candidate abbreviation mask is valid if it intersects with every difference mask. This reduces repeated string comparisons and allows efficient pruning while searching for the minimum abbreviation length.
Is Minimum Unique Word Abbreviation asked at Google/Amazon/Meta?
Minimum Unique Word Abbreviation is a well known hard interview problem that has appeared in interviews at companies such as Google and other large tech firms. It tests bit manipulation, backtracking, and search pruning techniques commonly expected for senior-level algorithm interviews.
What data structure is used in Minimum Unique Word Abbreviation?
The solution primarily uses bitmasks stored in arrays or lists to represent character differences between the target and dictionary words. Backtracking explores candidate masks, and bitwise AND operations quickly determine whether an abbreviation distinguishes the target from every dictionary entry.
What is the time complexity of Minimum Unique Word Abbreviation?
The optimized solution runs in roughly O(2^n * m) time, where n is the length of the target word and m is the number of dictionary words with the same length. Space complexity is O(m) for storing the difference masks. Bit operations make the validation step constant time for each dictionary word.