I think this problem is NP-hard. For proof, I'll reduce the **set cover** decision problem to it. The example there is:

```
U = {1, 2, 3, 4, 5}
S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}
```

Now I'd encode that for **Minimum Unique Word Abbreviation** like this:

```
target: "oooo"
dict: "looo" (word 1)
"lloo" (word 2)
"lolo" (word 3)
"olll" (word 4)
"oool" (word 5)
```

The five dictionary words correspond to the five elements of U. And every word has four letters, corresponding to the four subsets in S. You can see for example the second subset {2, 4} encoded as the second colum in the dictionary, which has `l`

in words 2 and 4 (and otherwise only `o`

).

(Side note: You can build an abbreviation by picking letters and then replacing the unpicked ones with numbers. For example, when you have `leetcode`

and pick the letters `l`

, `t`

and the last `e`

, you get `l2t3e`

. This way you can get all 2^{|word|} possible abbreviations from the 2^{|word|} possible ways of picking, as I've done in the first solution here.)

Now an optimal abbreviation for the target is "o2o", which we get by picking the first "o" because that distinguishes the target from words {1, 2, 3} and by picking the last "o" because that distinguishes the target from words {4, 5}. Just like picking the subsets {1, 2, 3} and {4, 5} cover all of U in the set cover problem.

A little problem is that if I switch the third and fourth element of S, then an optimal abbreviation picks the first and *third* "o", so instead of "o2o" we'd get "o1o1". That's a different length. So instead of the above encoding, I'd really do this, inserting "x" before and after each letter:

```
target: "xoxoxoxox"
dict: "xlxoxoxox"
"xlxlxoxox"
"xlxoxlxox"
"xoxlxlxlx"
"xoxoxoxlx"
```

Now "1o5o1" is an optimal abbreviation, and when I switch third and fourth element of S again, I instead get "1o3o3", which still has the same length.

To be precise and usable: When I pick k letters, the optimal abbreviation will have those k letters as well as k+1 numbers, so length 2k+1. That means minimizing the abbreviation length is equivalent to minimizing the number of picked letters, which is equivalent to minimizing the number of picked elements of S in the decision problem.

**Summary:** To solve a given **set cover** decision problem instance, I translate it to a **Minimum Unique Word Abbreviation** instance like above, and then from the computed optimal abbreviation, I subtract 1 from its length and divide it by 2 to get the number of picked letters, which is the minimum number of elements of S that cover U. And with that, I can directly answer the original set cover instance.

**Moral of the story:** Don't feel bad about writing a brute force solution :-)