# Shortest Distance to a Character
**Difficulty:** EASY
[External](https://leetcode.com/problems/shortest-distance-to-a-character)
Canonical: https://scaleengineer.com/dsa/problems/shortest-distance-to-a-character
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, String
---
## Problem
Given a string `s` and a character `c` that occurs in `s`, return _an array of integers_ `answer` _where_ `answer.length == s.length` _and_ `answer[i]` _is the **distance** from index_ `i` _to the **closest** occurrence of character_ `c` _in_ `s`.

The **distance** between two indices `i` and `j` is `abs(i - j)`, where `abs` is the absolute value function.

**Example 1:**

**Input:** s = "loveleetcode", c = "e"
**Output:** [3,2,1,0,1,0,0,1,2,2,1,0]
**Explanation:** The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

**Example 2:**

**Input:** s = "aaab", c = "b"
**Output:** [3,2,1,0]

**Constraints:**

* `1 <= s.length <= 104`
* `s[i]` and `c` are lowercase English letters.
* It is guaranteed that `c` occurs at least once in `s`.

# Approaches
## Brute Force
The most straightforward approach is to iterate through each character of the string. For each character, we perform another full scan of the string to find the closest occurrence of the target character `c`.
**Time:** O(N^2), where N is the length of the string `s`. For each of the N characters, we iterate through the entire string again, leading to a quadratic time complexity. · **Space:** O(N) for the output array `answer`. If the output array is not considered, the space complexity is O(1).
**Pros:** Very simple to conceptualize and implement.
**Cons:** Highly inefficient and will likely result in a 'Time Limit Exceeded' error for larger inputs as specified in the constraints.
### Explanation
For every index `i` in the string `s`, we initialize a minimum distance to a very large value. Then, we iterate through the entire string again with an index `j`. If the character at index `j` is the target character `c`, we calculate the distance `abs(i - j)` and update our minimum distance if this new distance is smaller. After checking all `j`'s for a given `i`, the resulting minimum distance is stored in our answer array at index `i`.

```java
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int minDistance = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == c) {
                    minDistance = Math.min(minDistance, Math.abs(i - j));
                }
            }
            answer[i] = minDistance;
        }

        return answer;
    }
}
```
### Algorithm
- Initialize an integer array `answer` with the same length as `s`.
- Loop through each index `i` from `0` to `s.length() - 1`.
- Inside the loop, initialize `minDistance` to `Integer.MAX_VALUE`.
- Start a nested loop for each index `j` from `0` to `s.length() - 1`.
- If `s.charAt(j)` is equal to `c`, update `minDistance` with `Math.min(minDistance, Math.abs(i - j))`.
- After the inner loop, set `answer[i] = minDistance`.
- Return the `answer` array.

## Pre-computation of 'c' Indices
To improve upon the brute-force method, we can avoid repeatedly scanning the string for the character `c`. We can first iterate through the string once to find all indices where `c` appears and store them in a list. Then, for each index `i` of the string, we find the minimum distance to an index in our pre-computed list.
**Time:** O(N log K), where N is the length of `s` and K is the number of occurrences of `c`. The initial scan to find indices is O(N). Then, for each of the N indices, we perform a binary search on the list of K indices, which takes O(log K) time. · **Space:** O(K) to store the `c_indices` list, plus O(N) for the output array. In the worst case, K can be N, so the space complexity is O(N).
**Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to pass within the time limits.
**Cons:** Slightly more complex to implement due to the binary search logic.; Not the most optimal solution in terms of time complexity.
### Explanation
First, we create a list, say `c_indices`, and populate it with all the indices where the character `c` is found in the string `s`. Since we iterate from left to right, this list will be naturally sorted.

Next, we iterate through the string `s` from `i = 0` to `n-1`. For each `i`, we need to find the index `j` in `c_indices` that minimizes `abs(i - j)`. Since `c_indices` is sorted, we can use binary search to find the insertion point of `i`. The two candidates for the closest index will be the one at the insertion point and the one just before it. We calculate the distance to both and take the minimum.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        List<Integer> cIndices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                cIndices.add(i);
            }
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int insertionPoint = Collections.binarySearch(cIndices, i);
            if (insertionPoint >= 0) {
                answer[i] = 0;
            } else {
                insertionPoint = -(insertionPoint + 1);
                int dist1 = Integer.MAX_VALUE;
                if (insertionPoint < cIndices.size()) {
                    dist1 = cIndices.get(insertionPoint) - i;
                }
                int dist2 = Integer.MAX_VALUE;
                if (insertionPoint > 0) {
                    dist2 = i - cIndices.get(insertionPoint - 1);
                }
                answer[i] = Math.min(dist1, dist2);
            }
        }
        return answer;
    }
}
```
### Algorithm
- Create a list `c_indices` to store indices of character `c`.
- Iterate through `s` and populate `c_indices`.
- Initialize an integer array `answer` with the same length as `s`.
- Loop through each index `i` from `0` to `s.length() - 1`.
- For each `i`, perform a binary search on `c_indices` to find the closest occurrence of `c`.
- The closest `c` will be at the insertion point or the element before it. Calculate the distances to both and take the minimum.
- Store this minimum distance in `answer[i]`.
- Return the `answer` array.

## Two-Pass Linear Scan
The most optimal solution involves making two passes over the string. The first pass calculates the distances from each character to the nearest `c` on its left. The second pass calculates the distances to the nearest `c` on its right. The final answer for each position is the minimum of these two calculated distances.
**Time:** O(N), where N is the length of the string `s`. We perform two separate linear scans of the string, which results in O(N) + O(N) = O(N) time. · **Space:** O(N) for the output array `answer`. Excluding the output array, the space complexity is O(1) as we only use a few variables.
**Pros:** Optimal time complexity of O(N).; Simple to implement and understand.; Efficient in terms of space, using only constant extra space (excluding the output array).
**Cons:** Requires two passes over the input string, which might be a slight disadvantage in scenarios where data can only be streamed once, though not applicable here.
### Explanation
We can solve this problem in linear time by breaking it down into two simpler problems:
1. Find the distance to the nearest `c` on the left for each character.
2. Find the distance to the nearest `c` on the right for each character.
The final answer is the minimum of these two values.

**Pass 1 (Left to Right):**
We initialize a result array `ans` and a variable `pos` to track the last seen index of `c` (initialized to a very small number, e.g., `-n`). We iterate from left to right. If `s[i] == c`, we update `pos = i`. For each `i`, we set `ans[i] = i - pos`.

**Pass 2 (Right to Left):**
We now iterate from right to left. We reset `pos` to a very large number (e.g., `2*n`). If `s[i] == c`, we update `pos = i`. For each `i`, we update `ans[i]` by taking `min(ans[i], pos - i)`. This second pass effectively considers the nearest `c` from the right.

After both passes, `ans` will contain the shortest distance for each character.

```java
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] answer = new int[n];
        int pos = -n; // Initialize to a position far to the left

        // First pass: left to right
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                pos = i;
            }
            answer[i] = i - pos;
        }

        // Second pass: right to left
        pos = n * 2; // Initialize to a position far to the right
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                pos = i;
            }
            answer[i] = Math.min(answer[i], pos - i);
        }

        return answer;
    }
}
```
### Algorithm
- Initialize an integer array `answer` of size `n` and a position variable `pos = -n`.
- **First Pass (Left to Right):** Iterate `i` from `0` to `n-1`.
- If `s.charAt(i) == c`, update `pos = i`.
- Set `answer[i] = i - pos`.
- **Second Pass (Right to Left):** Reset `pos` to a large value like `2*n`.
- Iterate `i` from `n-1` down to `0`.
- If `s.charAt(i) == c`, update `pos = i`.
- Update `answer[i] = Math.min(answer[i], pos - i)`.
- Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  int[] shortestToChar(String s, char c) {
    int n = s.length();
    int[] ans = new int[n];
    final int inf = 1 << 30;
    Arrays.fill(ans, inf);
    for (int i = 0, pre = -inf; i < n; ++i) {
      if (s.charAt(i) == c) {
        pre = i;
      }
      ans[i] = Math.min(ans[i], i - pre);
    }
    for (int i = n - 1, suf = inf; i >= 0; --i) {
      if (s.charAt(i) == c) {
        suf = i;
      }
      ans[i] = Math.min(ans[i], suf - i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> shortestToChar(string s, char c) {
    int n = s.size();
    const int inf = 1 << 30;
    vector<int> ans(n, inf);
    for (int i = 0, pre = -inf; i < n; ++i) {
      if (s[i] == c) {
        pre = i;
      }
      ans[i] = min(ans[i], i - pre);
    }
    for (int i = n - 1, suf = inf; ~i; --i) {
      if (s[i] == c) {
        suf = i;
      }
      ans[i] = min(ans[i], suf - i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]: n = len(s) ans = [n] * n pre = - inf for i, ch in enumerate(s): if ch == c: pre = i ans[i] = min(ans[i], i - pre) suf = inf for i in range(n - 1, - 1, - 1): if s[i] == c: suf = i ans[i] = min(ans[i], suf - i) return ans

```