# LeetCode 527: Word Abbreviation

## Problem Restatement

We are given an array of distinct lowercase words. For each word, we need to return its minimal unique abbreviation, while keeping the output in the same order as the input. The abbreviation starts with a prefix, then the number of abbreviated middle characters, then the last character. If the abbreviation is not shorter than the original word, we keep the original word.

For example:

```python
"internal" -> "i6l"
```

because there are `6` characters between `i` and `l`.

But abbreviations must be unique. If two words conflict, we increase their prefix length until the abbreviations become unique.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of distinct strings `words` |
| Output | A list of abbreviations |
| Order | Output must match the original input order |
| Constraint | `1 <= words.length <= 400` |
| Word length | `2 <= words[i].length <= 400` |

Function shape:

```python
def wordsAbbreviation(words: list[str]) -> list[str]:
    ...
```

## Examples

Input:

```python
words = ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
```

Output:

```python
["l2e", "god", "internal", "me", "i6t", "interval", "inte4n", "f2e", "intr4n"]
```

Some words stay unchanged.

For example:

```python
"god"
```

Its abbreviation would be:

```python
"g1d"
```

This has the same length as `"god"`, so we keep `"god"`.

The words `"internal"` and `"interval"` also need careful handling because they share length, first letter, and last letter patterns that can create conflicts.

## First Thought: Simulate Conflicts

A direct method is:

1. Start every word with prefix length `1`.
2. Build its abbreviation.
3. Find duplicate abbreviations.
4. Increase the prefix length for every word in a duplicate group.
5. Repeat until all abbreviations are unique.

This works, but repeated duplicate scanning can be clumsy.

We can do better by observing which words can conflict.

## Key Insight

Two words can only have the same abbreviation if they have:

1. The same length.
2. The same first character.
3. The same last character.

For example:

```python
"internal"
"interval"
```

Both have length `8`, start with `i`, and end with `l`.

So they may conflict.

But:

```python
"like"
"face"
```

cannot conflict because they start and end differently.

This means we can group words by:

```python
(length, first_character, last_character)
```

Then solve conflicts only inside each group.

Inside a group, the shortest unique prefix for a word is one character longer than the longest common prefix it shares with any other word in that group.

A trie is a clean way to compute that prefix length.

## Algorithm

Group all words by:

```python
(len(word), word[0], word[-1])
```

For each group:

1. Insert every word into a trie.
2. Each trie node stores how many words pass through it.
3. For each word, walk through the trie until reaching a node with count `1`.
4. That position gives the shortest unique prefix.
5. Build the abbreviation using that prefix.
6. If the abbreviation is not shorter than the original word, keep the original word.

The abbreviation helper is:

```python
prefix + count + last_char
```

where:

```python
count = len(word) - len(prefix) - 1
```

If `count <= 1`, the abbreviation usually will not save space.

## Correctness

Words from different groups cannot produce the same abbreviation because any abbreviation preserves the word length, first character, and last character. Therefore, resolving conflicts inside each group is enough.

Inside one group, the trie stores how many words share every prefix. When we walk through a word and find the first trie node with count `1`, that prefix belongs only to this word among all words in the group.

Using a shorter prefix would end at a node with count greater than `1`, which means at least one other word shares that prefix. Since all words in the group also share length and last character, the abbreviation would still conflict.

Therefore, the first prefix with count `1` gives the minimal unique abbreviation prefix for that word.

Finally, if the abbreviation is not shorter than the original word, the algorithm returns the original word, matching the problem rule.

## Complexity

Let:

```python
N = number of words
L = maximum word length
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(N * L)` | Each word is inserted into and searched in a trie |
| Space | `O(N * L)` | The tries may store all characters |

## Implementation

```python
from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Solution:
    def wordsAbbreviation(self, words: list[str]) -> list[str]:
        n = len(words)
        ans = [""] * n

        groups = defaultdict(list)

        for i, word in enumerate(words):
            key = (len(word), word[0], word[-1])
            groups[key].append(i)

        for indices in groups.values():
            root = TrieNode()

            for idx in indices:
                self._insert(root, words[idx])

            for idx in indices:
                word = words[idx]
                prefix_len = self._unique_prefix_length(root, word)
                ans[idx] = self._abbr(word, prefix_len)

        return ans

    def _insert(self, root: TrieNode, word: str) -> None:
        node = root

        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()

            node = node.children[ch]
            node.count += 1

    def _unique_prefix_length(self, root: TrieNode, word: str) -> int:
        node = root

        for i, ch in enumerate(word):
            node = node.children[ch]

            if node.count == 1:
                return i + 1

        return len(word)

    def _abbr(self, word: str, prefix_len: int) -> str:
        abbreviated_count = len(word) - prefix_len - 1
        abbr = word[:prefix_len] + str(abbreviated_count) + word[-1]

        if len(abbr) >= len(word):
            return word

        return abbr
```

## Code Explanation

The answer array keeps the original order:

```python
ans = [""] * n
```

We group by length, first letter, and last letter:

```python
key = (len(word), word[0], word[-1])
```

This avoids comparing words that can never conflict.

The trie insertion increments `count` after moving into each character node:

```python
node = node.children[ch]
node.count += 1
```

So `node.count` means how many words share the prefix ending at this node.

To find a unique prefix, we walk through the word:

```python
if node.count == 1:
    return i + 1
```

The first prefix whose count is `1` is the shortest prefix that separates this word from every other word in its group.

The abbreviation is built as:

```python
word[:prefix_len] + str(abbreviated_count) + word[-1]
```

If the abbreviation does not reduce length, we return the original word.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.wordsAbbreviation(
        ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
    ) == ["l2e", "god", "internal", "me", "i6t", "interval", "inte4n", "f2e", "intr4n"]

    assert s.wordsAbbreviation(["aa", "aaa"]) == ["aa", "aaa"]

    assert s.wordsAbbreviation(["abcdef", "abndef"]) == ["abc2f", "abn2f"]

    assert s.wordsAbbreviation(["apple"]) == ["a3e"]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Main sample | Checks grouped conflicts |
| `["aa", "aaa"]` | Checks short words that should stay unchanged |
| `["abcdef", "abndef"]` | Checks prefix expansion |
| Single word | Checks simple abbreviation without conflict |