Problem

Given a string s and a character c that occurs in s, return an array of integersanswer whereanswer.length == s.length andanswer[i]_is thedistance from index _i _to theclosest occurrence of character _c ins.

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

Examples

Example 1

1
2
3
4
5
6
7

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

1
2

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

Constraints

  • 1 <= s.length <= 10^4
  • s[i] and c are lowercase English letters.
  • It is guaranteed that c occurs at least once in s.

Solution

Method 1 – Two-Pass (Left and Right)

Intuition

For each index, the shortest distance to character c is the minimum of the distance to the closest c on the left and the closest c on the right. We can compute this efficiently with two passes.

Approach

  1. First pass left-to-right: for each index, track the last seen c and compute the distance.
  2. Second pass right-to-left: update the answer with the minimum distance to the next c on the right.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        int prev = -n;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == c) prev = i;
            ans[i] = i - prev;
        }
        prev = 2*n;
        for (int i = n-1; i >= 0; --i) {
            if (s.charAt(i) == c) prev = i;
            ans[i] = Math.min(ans[i], Math.abs(i - prev));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def shortestToChar(self, s: str, c: str) -> list[int]:
        n = len(s)
        ans = [0]*n
        prev = -n
        for i in range(n):
            if s[i]==c: prev = i
            ans[i] = i - prev
        prev = 2*n
        for i in range(n-1,-1,-1):
            if s[i]==c: prev = i
            ans[i] = min(ans[i], abs(i-prev))
        return ans

Complexity

  • ⏰ Time complexity: O(n) — Two passes through the string.
  • 🧺 Space complexity: O(n) — For the answer array.