> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Unique Word Abbreviation

> Tested Python solution for LeetCode 411 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 411, [Hard](/catalog/hard). Topics: [Bit Manipulation](/catalog/topics/bit-manipulation), [Array](/catalog/topics/array), [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking). [View on LeetCode](https://leetcode.com/problems/minimum-unique-word-abbreviation/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 411   # by problem number
lcpy gen -s minimum_unique_word_abbreviation   # by problem name
```

## 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*.

### Examples

```
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".
```

```
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`
* `log_2(n) + m <= 21` if `n > 0`
* `target` and `dictionary[i]` consist of lowercase English letters.
* `dictionary` does not contain `target`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_unique_word_abbreviation/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_unique_word_abbreviation/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(2^m * n * m) — enumerate letter subsets, check against dictionary
    # Space: O(m) for the abbreviation buffer
    def min_abbreviation(self, target: str, dictionary: list[str]) -> str:
        m = len(target)
        words = [w for w in dictionary if len(w) == m]

        def abbr_from_mask(mask: int) -> str:
            parts: list[str] = []
            run = 0
            for i, ch in enumerate(target):
                if mask >> i & 1:
                    if run:
                        parts.append(str(run))
                        run = 0
                    parts.append(ch)
                else:
                    run += 1
            if run:
                parts.append(str(run))
            return "".join(parts)

        def matches(abbr: str, w: str) -> bool:
            i = j = 0
            while i < len(abbr) and j < len(w):
                if abbr[i].isdigit():
                    if abbr[i] == "0":
                        return False
                    k = 0
                    while i < len(abbr) and abbr[i].isdigit():
                        k = k * 10 + int(abbr[i])
                        i += 1
                    j += k
                else:
                    if w[j] != abbr[i]:
                        return False
                    i += 1
                    j += 1
            return i == len(abbr) and j == len(w)

        def conflicts(abbr: str) -> bool:
            return any(matches(abbr, w) for w in words)

        best_abbr = ""
        best_len = m + 1
        for mask in range(1 << m):
            candidate = abbr_from_mask(mask)
            candidate_len = sum(1 for c in candidate if c.isalpha()) + sum(
                1 for c in candidate if c.isdigit()
            )
            if candidate_len >= best_len:
                continue
            if not conflicts(candidate):
                best_abbr, best_len = candidate, candidate_len
        return best_abbr
```

## Complexity

| Time | Space |
| - | - |
| O(2^m \* n \* m) — enumerate letter subsets, check against dictionary | O(m) for the abbreviation buffer |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.