Watch 10 video solutions for Minimum Unique Word Abbreviation, a hard level problem involving Array, String, Backtracking. This walkthrough by CrioDo has 304,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 21 if n > 0target and dictionary[i] consist of lowercase English letters.dictionary does not contain target.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.
| 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 |