# LeetCode 821: Shortest Distance to a Character

## Problem Restatement

We are given a string `s` and a character `c`.

The character `c` appears at least once in `s`.

For every index `i`, we need to find the shortest distance from `i` to any index where `s[index] == c`.

The distance between two indices `i` and `j` is:

```python
abs(i - j)
```

Return an array `answer`, where:

```python
answer[i] = distance from i to the closest c
```

The official constraints say `s` has length at most `10^4`, all characters are lowercase English letters, and `c` occurs at least once in `s`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` and a character `c` |
| Output | An integer array of length `len(s)` |
| Distance | `abs(i - j)` between two indices |
| Guarantee | `c` appears at least once in `s` |

## Examples

Example 1:

```python
s = "loveleetcode"
c = "e"
```

The character `"e"` appears at indices:

```python
3, 5, 6, 11
```

The closest distances are:

```python
[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
```

So the answer is:

```python
[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
```

Example 2:

```python
s = "aaab"
c = "b"
```

The only `"b"` is at index `3`.

So the answer is:

```python
[3, 2, 1, 0]
```

## First Thought: Check Every Occurrence

One simple approach is:

1. Store all positions where `s[i] == c`.
2. For every index `i`, compare it with every stored position.
3. Keep the minimum absolute distance.

This works, but it can be too slow.

If the string has length `n`, and many characters are equal to `c`, this can approach:

```python
O(n^2)
```

We can do better by scanning the string twice.

## Key Insight

For any index `i`, the closest occurrence of `c` is either:

1. The closest `c` on the left.
2. The closest `c` on the right.

So we can compute both directions separately.

First pass, left to right:

```python
distance to closest c on the left
```

Second pass, right to left:

```python
distance to closest c on the right
```

The answer for each index is the smaller of those two distances.

## Algorithm

Let:

```python
n = len(s)
answer = [n] * n
```

Use `n` as a large initial distance.

First pass:

1. Set `prev = -n`.
2. Scan from left to right.
3. Whenever `s[i] == c`, set `prev = i`.
4. Store:

```python
answer[i] = i - prev
```

Second pass:

1. Set `next_pos = 2 * n`.
2. Scan from right to left.
3. Whenever `s[i] == c`, set `next_pos = i`.
4. Update:

```python
answer[i] = min(answer[i], next_pos - i)
```

Return `answer`.

## Correctness

During the left-to-right pass, `prev` always stores the nearest occurrence of `c` at or before the current index. Therefore, `i - prev` is the distance from `i` to the closest `c` on its left side.

During the right-to-left pass, `next_pos` always stores the nearest occurrence of `c` at or after the current index. Therefore, `next_pos - i` is the distance from `i` to the closest `c` on its right side.

For any index, the closest occurrence of `c` must be either on the left or on the right. The algorithm takes the minimum of these two distances, so `answer[i]` becomes the shortest distance from index `i` to any occurrence of `c`.

Thus the returned array is correct.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the string twice |
| Space | `O(1)` extra | Apart from the output array, only two variables are used |

## Implementation

```python
class Solution:
    def shortestToChar(self, s: str, c: str) -> list[int]:
        n = len(s)
        answer = [n] * n

        prev = -n

        for i in range(n):
            if s[i] == c:
                prev = i

            answer[i] = i - prev

        next_pos = 2 * n

        for i in range(n - 1, -1, -1):
            if s[i] == c:
                next_pos = i

            answer[i] = min(answer[i], next_pos - i)

        return answer
```

## Code Explanation

We initialize the answer with a large value:

```python
answer = [n] * n
```

The first pass records distance to the nearest `c` on the left:

```python
prev = -n
```

Before any `c` has been seen, `prev` is far outside the string, so the distance is large.

Whenever we find `c`, we update `prev`:

```python
if s[i] == c:
    prev = i
```

Then we store the left-side distance:

```python
answer[i] = i - prev
```

The second pass records distance to the nearest `c` on the right:

```python
next_pos = 2 * n
```

Whenever we find `c`, we update `next_pos`:

```python
if s[i] == c:
    next_pos = i
```

Then we keep the smaller distance:

```python
answer[i] = min(answer[i], next_pos - i)
```

## Testing

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

    assert s.shortestToChar("loveleetcode", "e") == [
        3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0
    ]

    assert s.shortestToChar("aaab", "b") == [3, 2, 1, 0]

    assert s.shortestToChar("a", "a") == [0]

    assert s.shortestToChar("abcde", "c") == [2, 1, 0, 1, 2]

    assert s.shortestToChar("aaaaa", "a") == [0, 0, 0, 0, 0]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"loveleetcode"`, `"e"` | Official example with several target positions |
| `"aaab"`, `"b"` | Target appears only at the end |
| `"a"`, `"a"` | Minimum input |
| `"abcde"`, `"c"` | Target appears in the middle |
| `"aaaaa"`, `"a"` | Every index is already the target |