> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/bit-manipulation/411.-minimum-unique-word-abbreviation.md).

# 411. Minimum Unique Word Abbreviation

A string such as `"word"` contains the following abbreviations:

```
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
```

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the **smallest possible** length such that it does not conflict with abbreviations of the strings in the dictionary.

Each **number** or letter in the abbreviation is considered length = 1. For example, the abbreviation "a32bc" has length = 4.

**Note:**<br>

* In the case of multiple answers as shown in the second example below, you may return any one of them.
* Assume length of target string = **m**, and dictionary size = **n**. You may assume that **m ≤ 21**, **n ≤ 1000**, and **log2(n) + m ≤ 20**.

**Examples:**<br>

```cpp
"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")

"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").
```

```cpp
priority_queue<pair<int, string>, vector<pair<int, string> >, greater<pair<int, string> > > generate(const string& target) {
    priority_queue<pair<int, string>, vector<pair<int, string> >, greater<pair<int, string> > > res;
    for (int i = 0; i < pow(2, target.length()); ++i) {
        string cur;
        int cnt = 0, len = 0;
        for (int j = 0; j < target.length(); ++j) {
            if ((i >> j) & 1) ++cnt;
            else {
                if (cnt) {
                    cur += to_string(cnt);
                    cnt = 0;
                    ++len;
                }
                cur += target[j];
                ++len;
            }
        }
        if (cnt) {
            cur += to_string(cnt);
            ++len;
        }
        res.push(make_pair(len, cur));
    }
    return res;
}
bool valid(const string& word, const string& abbr) {
    int m = word.length(), n = abbr.length(), pos = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (abbr[i] >= '0' && abbr[i] <= '9') {
            if (cnt == 0 && abbr[i] == '0') return false;
            cnt = cnt * 10 + abbr[i] - '0';
        } else {
            pos += cnt;
            if (pos >= m || word[pos++] != abbr[i]) return false;
            cnt = 0;
        }
    }
    return pos + cnt == m;
}
string minAbbreviation(string target, vector<string>& dictionary) {
    if (dictionary.empty()) return to_string(static_cast<int>(target.length()));
    priority_queue<pair<int, string>, vector<pair<int, string> >, greater<pair<int, string> > > pq;
    pq = generate(target);
    while (!pq.empty()) {
        auto t = pq.top(); pq.pop();
        bool no_conflict = true;
        for (const string& word : dictionary) {
            if (valid(word, t.second)) {
                no_conflict = false;
                break;
            }
        }
        if (no_conflict) return t.second;
    }
    return "";
}
```