# LeetCode 320: Generalized Abbreviation

## Problem Restatement

We are given a lowercase string `word`.

Return all possible generalized abbreviations of `word`.

A generalized abbreviation replaces any number of non-overlapping and non-adjacent substrings with their lengths. For example, `"abcde"` can become `"a3e"`, `"1bcd1"`, `"5"`, or `"abcde"`. The input length is at most `15`, and the answer can be returned in any order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A lowercase string `word` |
| Output | All possible generalized abbreviations |
| Order | Any order is accepted |
| Constraint | `1 <= word.length <= 15` |

Function shape:

```python
def generateAbbreviations(word: str) -> list[str]:
    ...
```

## Examples

Example 1:

```python
word = "word"
```

Possible output:

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

Example 2:

```python
word = "a"
```

Output:

```python
["1", "a"]
```

For one character, we either abbreviate it as `1` or keep it as `"a"`.

## First Thought: Choose for Every Character

For each character, we have two choices:

1. Keep the character.
2. Abbreviate the character.

For example:

```python
word = "abc"
```

One choice pattern is:

```text
keep a, abbreviate b, keep c
```

This gives:

```python
"a1c"
```

Another pattern:

```text
abbreviate a, abbreviate b, abbreviate c
```

This gives:

```python
"3"
```

Adjacent abbreviated characters should be merged into one number. So `"111"` should become `"3"`.

That means we should not append `"1"` immediately every time we abbreviate a character. Instead, keep a running count of abbreviated characters.

## Key Insight

Use backtracking with three pieces of state:

| State | Meaning |
|---|---|
| `index` | Current position in `word` |
| `path` | Parts of the abbreviation already built |
| `count` | Number of consecutive abbreviated characters not yet written |

At every character, choose:

1. Abbreviate it: increase `count`.
2. Keep it: first flush `count` into `path`, then append the character.

At the end, flush any remaining count and save the abbreviation.

## Algorithm

Define:

```python
backtrack(index, path, count)
```

If `index == len(word)`:

1. If `count > 0`, append `str(count)`.
2. Join `path`.
3. Add the result to `answer`.

Otherwise, at `word[index]`:

Choice 1: abbreviate this character.

```python
backtrack(index + 1, path, count + 1)
```

Choice 2: keep this character.

1. If `count > 0`, append `str(count)`.
2. Append `word[index]`.
3. Recurse with `count = 0`.
4. Undo appended parts after recursion.

## Correctness

For every character, the algorithm makes exactly two choices: abbreviate it or keep it.

Therefore, every possible keep-or-abbreviate pattern is explored.

The `count` variable records a run of consecutive abbreviated characters. When a kept character appears, the algorithm writes the count before writing that character. At the end of the word, it also writes any remaining count. Thus each generated string uses the proper numeric abbreviation for every maximal run of abbreviated characters.

Every generated abbreviation corresponds to one unique choice pattern over the characters of `word`.

Every valid generalized abbreviation can also be described by choosing which characters are abbreviated and which are kept. The algorithm explores that exact choice pattern and produces the abbreviation.

Therefore, the algorithm returns all and only valid generalized abbreviations.

## Complexity

Let `n = len(word)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * 2^n)` | There are `2^n` abbreviations, and building each output can cost `O(n)` |
| Space | `O(n)` | Recursion depth and current path, excluding the output list |

The output itself contains `2^n` strings.

## Implementation

```python
class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        answer = []
        n = len(word)

        def backtrack(index: int, path: list[str], count: int) -> None:
            if index == n:
                original_len = len(path)

                if count > 0:
                    path.append(str(count))

                answer.append("".join(path))

                while len(path) > original_len:
                    path.pop()

                return

            backtrack(index + 1, path, count + 1)

            original_len = len(path)

            if count > 0:
                path.append(str(count))

            path.append(word[index])

            backtrack(index + 1, path, 0)

            while len(path) > original_len:
                path.pop()

        backtrack(0, [], 0)

        return answer
```

## Code Explanation

We store all generated abbreviations in:

```python
answer = []
```

The recursive function is:

```python
def backtrack(index: int, path: list[str], count: int) -> None:
```

`index` tells us which character we are deciding.

`path` stores already written pieces.

`count` stores abbreviated characters that have not yet been written as a number.

When we reach the end:

```python
if index == n:
```

we flush `count` if needed.

```python
if count > 0:
    path.append(str(count))
```

Then we join the path.

```python
answer.append("".join(path))
```

The first branch abbreviates the current character.

```python
backtrack(index + 1, path, count + 1)
```

No string piece is added yet. We only increase the pending abbreviation count.

The second branch keeps the current character.

```python
if count > 0:
    path.append(str(count))

path.append(word[index])
```

If there is a pending count, it must be written before the kept character.

Then recurse with `count = 0`.

```python
backtrack(index + 1, path, 0)
```

After recursion, restore `path` so the next branch starts cleanly.

```python
while len(path) > original_len:
    path.pop()
```

## Bit Mask Implementation

Because `word.length <= 15`, we can also enumerate all bit masks.

A `1` bit means abbreviate the character.

A `0` bit means keep the character.

```python
class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        n = len(word)
        answer = []

        for mask in range(1 << n):
            parts = []
            count = 0

            for i in range(n):
                if mask & (1 << i):
                    count += 1
                else:
                    if count > 0:
                        parts.append(str(count))
                        count = 0

                    parts.append(word[i])

            if count > 0:
                parts.append(str(count))

            answer.append("".join(parts))

        return answer
```

This is compact and follows the same keep-or-abbreviate idea.

## Testing

```python
def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(s.generateAbbreviations("a")) == normalize([
        "1",
        "a",
    ])

    assert normalize(s.generateAbbreviations("ab")) == normalize([
        "2",
        "1b",
        "a1",
        "ab",
    ])

    assert normalize(s.generateAbbreviations("word")) == normalize([
        "4",
        "3d",
        "2r1",
        "2rd",
        "1o2",
        "1o1d",
        "1or1",
        "1ord",
        "w3",
        "w2d",
        "w1r1",
        "w1rd",
        "wo2",
        "wo1d",
        "wor1",
        "word",
    ])

    assert len(s.generateAbbreviations("abc")) == 8
    assert len(s.generateAbbreviations("abcd")) == 16

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"a"` | Smallest input |
| `"ab"` | Checks adjacent abbreviation merging |
| `"word"` | Standard example |
| `"abc"` | Confirms `2^n` outputs |
| `"abcd"` | Confirms output count grows by choices |