Skip to main content
Talentd

Minimum Unique Word Abbreviation - Solution & Explanation

HardPremiumFree on FleetCodeArrayStringBacktrackingBit Manipulation4 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.length
  • n == dictionary.length
  • 1 <= m <= 21
  • 0 <= n <= 1000
  • 1 <= dictionary[i].length <= 100
  • log2(n) + m <= 21 if n > 0
  • target and dictionary[i] consist of lowercase English letters.
  • dictionary does not contain target.

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Abbreviation GenerationO(2^n * n)O(n)Good for understanding how abbreviations are formed and validated
Bitmask + Backtracking with Conflict MasksO(2^n * m)O(m)Best general solution when dictionary size is moderate
Bitmask Search with PruningO(2^n) average with pruningO(m)Preferred interview solution for minimizing abbreviation length efficiently

Video Solution

Leetcode 320. Generalized Abbreviation && 411. Minimum Unique Word Abbreviation • Algorithms for Big Bucks • 1,255 views views

Watch 2 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Unique Word Abbreviation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Generalized Abbreviation

Next

Valid Word Abbreviation