# LeetCode 748: Shortest Completing Word

## Problem Restatement

We are given a string `licensePlate` and a list of words.

A word is called a completing word if it contains every letter from `licensePlate`.

When reading `licensePlate`:

- Ignore digits.
- Ignore spaces.
- Treat uppercase and lowercase letters as the same.
- If a letter appears multiple times, the word must contain it at least that many times.

We need to return the shortest completing word from `words`.

If there are multiple shortest completing words, return the one that appears first in `words`. The problem guarantees that an answer exists.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `licensePlate` and `words` |
| Output | The shortest completing word |
| Ignored characters | Digits and spaces in `licensePlate` |
| Case handling | Case-insensitive |
| Tie rule | Return the first shortest word in `words` |

Example function shape:

```python
def shortestCompletingWord(
    licensePlate: str,
    words: list[str],
) -> str:
    ...
```

## Examples

### Example 1

```python
licensePlate = "1s3 PSt"
words = ["step", "steps", "stripe", "stepple"]
```

After removing digits and spaces, and converting to lowercase, the required letters are:

```text
s, p, s, t
```

So the required counts are:

| Letter | Count |
|---|---:|
| s | 2 |
| p | 1 |
| t | 1 |

Check the words:

| Word | Completing? | Why |
|---|---|---|
| `"step"` | No | Has only one `s` |
| `"steps"` | Yes | Has `s` twice, `p` once, `t` once |
| `"stripe"` | No | Has only one `s` |
| `"stepple"` | No | Has only one `s` |

The answer is:

```python
"steps"
```

### Example 2

```python
licensePlate = "1s3 456"
words = ["looks", "pest", "stew", "show"]
```

The required letters are:

```text
s
```

The shortest words containing `s` are `"pest"` and `"stew"`.

Both have length `4`, but `"pest"` appears first.

The answer is:

```python
"pest"
```

## First Thought: Compare Each Word

We can preprocess the license plate once.

For each word, count its letters and check whether it contains enough of every required letter.

Because there are only 26 lowercase English letters, this comparison is small and simple.

## Key Insight

This is a frequency counting problem.

Build a required count array:

```python
need[letter]
```

Then for each candidate word, build:

```python
have[letter]
```

The word is completing if for every letter:

```python
have[letter] >= need[letter]
```

To preserve the tie rule, scan `words` in order and update the answer only when the valid word is strictly shorter than the current answer.

## Algorithm

1. Create an array `need` of size `26`.
2. For each character in `licensePlate`:
   - If it is a letter, convert it to lowercase.
   - Increment its count in `need`.
3. Initialize `answer = None`.
4. For each `word` in `words`:
   - If `answer` exists and `len(word) >= len(answer)`, skip it.
   - Count letters in `word`.
   - If the word satisfies all required counts, set `answer = word`.
5. Return `answer`.

## Correctness

The `need` array records exactly the letters required by the license plate, ignoring digits and spaces and treating letters case-insensitively.

For each word, the algorithm counts its letters and compares those counts with `need`. A word is accepted only if every required letter appears at least as many times as needed. This matches the definition of a completing word.

The algorithm scans `words` from left to right. It updates the answer only when it finds a completing word with strictly smaller length. Therefore, when two completing words have the same shortest length, the earlier one remains selected.

Since the problem guarantees that at least one completing word exists, the final answer is the shortest completing word with the required tie behavior.

## Complexity

Let `n = len(words)` and let `L` be the maximum word length.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(len(licensePlate) + n * L)` | Count the license plate once, then count each candidate word |
| Space | `O(1)` | Count arrays have fixed size `26` |

The output string itself is not counted as extra working space.

## Implementation

```python
class Solution:
    def shortestCompletingWord(
        self,
        licensePlate: str,
        words: list[str],
    ) -> str:
        need = [0] * 26

        for ch in licensePlate:
            if ch.isalpha():
                index = ord(ch.lower()) - ord("a")
                need[index] += 1

        answer = None

        for word in words:
            if answer is not None and len(word) >= len(answer):
                continue

            have = [0] * 26

            for ch in word:
                index = ord(ch) - ord("a")
                have[index] += 1

            ok = True

            for i in range(26):
                if have[i] < need[i]:
                    ok = False
                    break

            if ok:
                answer = word

        return answer
```

## Code Explanation

The required letter counts are stored here:

```python
need = [0] * 26
```

For every character in the license plate, we only keep letters:

```python
if ch.isalpha():
```

Then we convert to lowercase and count it:

```python
index = ord(ch.lower()) - ord("a")
need[index] += 1
```

For each word, we can skip it if it cannot improve the current answer:

```python
if answer is not None and len(word) >= len(answer):
    continue
```

This keeps the first word when there is a tie.

Then we count the word letters:

```python
have = [0] * 26

for ch in word:
    index = ord(ch) - ord("a")
    have[index] += 1
```

Finally, compare the two arrays:

```python
for i in range(26):
    if have[i] < need[i]:
        ok = False
        break
```

If every required count is satisfied, this word becomes the best answer so far.

## Testing

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

    assert s.shortestCompletingWord(
        "1s3 PSt",
        ["step", "steps", "stripe", "stepple"],
    ) == "steps"

    assert s.shortestCompletingWord(
        "1s3 456",
        ["looks", "pest", "stew", "show"],
    ) == "pest"

    assert s.shortestCompletingWord(
        "Ah71752",
        ["suggest", "letter", "of", "husband", "easy", "education", "drug"],
    ) == "husband"

    assert s.shortestCompletingWord(
        "OgEu755",
        ["enough", "these", "play", "wide", "wonder", "box", "arrive", "money", "tax", "thus"],
    ) == "enough"

    assert s.shortestCompletingWord(
        "aBc 12c",
        ["abccdef", "cbca", "caaacab"],
    ) == "cbca"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"1s3 PSt"` | Requires repeated `s` and ignores case |
| `"1s3 456"` | Tie chooses earlier shortest word |
| `"Ah71752"` | Mixed digits and uppercase letters |
| `"OgEu755"` | Multiple required letters |
| `"aBc 12c"` | Repeated `c`, shortest valid word wins |