# LeetCode 1048: Longest String Chain

## Problem Restatement

We are given an array of words.

A word `wordA` is a predecessor of `wordB` if we can insert exactly one letter anywhere in `wordA` to make it equal to `wordB`.

A word chain is a sequence of words `[word_1, word_2, ..., word_k]` where each `word_i` is a predecessor of `word_{i+1}`.

Return the length of the longest word chain.

The official constraints state that `1 <= words.length <= 1000`, `1 <= words[i].length <= 16`, and `words[i]` contains only lowercase English letters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `words` |
| Output | Length of longest word chain |

Function shape:

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

## Examples

Example 1:

```python
words = ["a", "b", "ba", "bca", "bda", "bdca"]
```

Chain: `"a"` → `"ba"` → `"bda"` → `"bdca"`. Length 4.

Answer:

```python
4
```

## Key Insight

Sort words by length. Then for each word, try removing each character to get a possible predecessor. If that predecessor exists in our DP map, update the current word's chain length.

## Algorithm

1. Sort `words` by length.
2. `dp[word]` = longest chain ending at `word`.
3. For each word (in sorted order):
   - For each position `i`, form `prev = word[:i] + word[i+1:]`.
   - `dp[word] = max(dp[word], dp.get(prev, 0) + 1)`.
4. Return the maximum value in `dp`.

## Correctness

Since we process words in order of increasing length, when we process `word`, all potential predecessors (shorter by one letter) have already been processed and their DP values computed.

For each predecessor `prev` of `word`, the chain length through `prev` is `dp[prev] + 1`. We take the maximum.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * L^2)` | For each word, try removing each character (`O(L)`) and string slicing (`O(L)`) |
| Space | `O(n * L)` | DP dictionary |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        words.sort(key=len)
        dp = {}
        best = 1

        for word in words:
            dp[word] = 1
            for i in range(len(word)):
                prev = word[:i] + word[i+1:]
                if prev in dp:
                    dp[word] = max(dp[word], dp[prev] + 1)
            best = max(best, dp[word])

        return best
```

## Testing

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

    assert s.longestStrChain(["a","b","ba","bca","bda","bdca"]) == 4
    assert s.longestStrChain(["xbc","pcxbcf","xb","cxbc","pcxbc"]) == 5
    assert s.longestStrChain(["a"]) == 1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `["a","b","ba","bca","bda","bdca"]` | `4` | Chain of length 4 |
| 5-word chain | `5` | All 5 words form a chain |
| Single word | `1` | No predecessors |