# LeetCode 245: Shortest Word Distance III

## Problem Restatement

We are given a list of words called `wordsDict` and two words, `word1` and `word2`.

We need to return the shortest distance between the two words in the list.

The distance between two words is the absolute difference between their indices.

Unlike the previous problem, `word1` and `word2` may be the same word.

If they are the same, we must use two different occurrences.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `wordsDict`, `word1`, `word2` |
| Output | The minimum index distance |
| Special case | `word1` may equal `word2` |
| Requirement | Two occurrences must use different indices |

Example function shape:

```python
def shortestWordDistance(wordsDict: list[str], word1: str, word2: str) -> int:
    ...
```

## Examples

Example 1:

```python
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "coding"
```

`"makes"` appears at indices `1` and `4`.

`"coding"` appears at index `3`.

The closest distance is:

```python
abs(4 - 3) = 1
```

So the answer is:

```python
1
```

Example 2:

```python
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "makes"
```

Now both target words are the same.

We must use two different occurrences.

The word `"makes"` appears at indices:

```python
1 and 4
```

The distance is:

```python
abs(4 - 1) = 3
```

So the answer is:

```python
3
```

## First Thought

For different words, we can reuse the solution from LeetCode 243.

We scan from left to right and store the latest index of each word.

But when:

```python
word1 == word2
```

the previous logic breaks.

We cannot store only one index and compare it with itself.

Instead, we must compare consecutive occurrences of the same word.

## Key Insight

There are two cases.

### Case 1: Different Words

If:

```python
word1 != word2
```

we use the normal approach:

```python
last1 = latest index of word1
last2 = latest index of word2
```

Every time both indices exist, update the answer.

### Case 2: Same Word

If:

```python
word1 == word2
```

then we only care about the distance between consecutive occurrences.

For example:

```python
["a", "x", "a", "x", "a"]
```

The shortest distance must come from neighboring `"a"` positions.

So we track:

```python
previous occurrence of the word
```

Whenever we see the word again, compute the distance to the previous occurrence.

## Algorithm

### Different Words

1. Initialize:

```python
last1 = -1
last2 = -1
answer = infinity
```

2. Scan the array.
3. Update the latest index for each word.
4. Whenever both indices exist, update the minimum distance.

### Same Word

1. Initialize:

```python
previous = -1
answer = infinity
```

2. Scan the array.
3. When the word appears:
   - If `previous` exists, compute the distance.
   - Update `previous`.

## Correctness

### Different Words

At every step, `last1` and `last2` store the latest occurrences of `word1` and `word2`.

When a new occurrence appears, the closest possible partner among earlier positions is the latest occurrence of the other word. Any older occurrence is farther away.

Thus, every potentially optimal pair is checked.

### Same Word

Suppose the target word appears at indices:

```python
i1 < i2 < i3 < ...
```

The shortest distance must occur between two consecutive occurrences.

Why?

For any non-consecutive pair:

```python
ik and ij where j > k + 1
```

there exists another occurrence between them, so:

```python
ij - ik
```

is larger than at least one consecutive distance.

Therefore, checking consecutive occurrences is sufficient.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | Only a few variables are stored |

## Implementation

```python
class Solution:
    def shortestWordDistance(
        self,
        wordsDict: list[str],
        word1: str,
        word2: str,
    ) -> int:

        answer = float("inf")

        if word1 == word2:
            previous = -1

            for i, word in enumerate(wordsDict):
                if word == word1:
                    if previous != -1:
                        answer = min(answer, i - previous)

                    previous = i

        else:
            last1 = -1
            last2 = -1

            for i, word in enumerate(wordsDict):
                if word == word1:
                    last1 = i

                elif word == word2:
                    last2 = i

                if last1 != -1 and last2 != -1:
                    answer = min(answer, abs(last1 - last2))

        return answer
```

## Code Explanation

We start with:

```python
answer = float("inf")
```

This stores the best distance found so far.

Then we split into two cases.

### Same Word Case

```python
if word1 == word2:
```

We store the previous occurrence:

```python
previous = -1
```

Whenever we see the word again:

```python
if previous != -1:
    answer = min(answer, i - previous)
```

Then we update:

```python
previous = i
```

### Different Word Case

We store the latest index of each word:

```python
last1 = -1
last2 = -1
```

When either word appears, update its latest index.

If both exist, compute:

```python
abs(last1 - last2)
```

and update the answer.

## Testing

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

    assert s.shortestWordDistance(
        ["practice", "makes", "perfect", "coding", "makes"],
        "makes",
        "coding",
    ) == 1

    assert s.shortestWordDistance(
        ["practice", "makes", "perfect", "coding", "makes"],
        "makes",
        "makes",
    ) == 3

    assert s.shortestWordDistance(
        ["a", "b", "a"],
        "a",
        "a",
    ) == 2

    assert s.shortestWordDistance(
        ["a", "x", "b", "a", "b"],
        "a",
        "b",
    ) == 1

    assert s.shortestWordDistance(
        ["x", "a", "x", "a", "x", "a"],
        "a",
        "a",
    ) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Different words | Standard case |
| Same word | Core special case |
| Two occurrences only | Smallest same-word case |
| Multiple mixed occurrences | Confirms updates work correctly |
| Repeated same word | Confirms consecutive comparison logic |