Shortest Distance to a Character

Problem Statement

Given a string s and a character c that occurs in s, return an array answer where answer[i] is the distance from index i to the nearest occurrence of c.

Example

Input:  s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Approach (Two-Pass Scan)

Do two linear passes with a moving reference pointer. In the left-to-right pass, track the last index where c appeared and record distance from the left. In the right-to-left pass, do the same from the right and keep the minimum.

Complexity

• Time: O(n)
• Space: O(n) for the output

Solution Code

Python

def shortestToChar(s, c):
    n = len(s)
    res = [n] * n
    prev = float('-inf')
    for i in range(n):            # left to right
        if s[i] == c:
            prev = i
        res[i] = i - prev
    prev = float('inf')
    for i in range(n - 1, -1, -1): # right to left
        if s[i] == c:
            prev = i
        res[i] = min(res[i], prev - i)
    return res

Java

int[] shortestToChar(String s, char c) {
    int n = s.length();
    int[] res = new int[n];
    int prev = Integer.MIN_VALUE / 2;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == c) prev = i;
        res[i] = i - prev;
    }
    prev = Integer.MAX_VALUE / 2;
    for (int i = n - 1; i >= 0; i--) {
        if (s.charAt(i) == c) prev = i;
        res[i] = Math.min(res[i], prev - i);
    }
    return res;
}

C++

vector<int> shortestToChar(string s, char c) {
    int n = s.size();
    vector<int> res(n);
    int prev = INT_MIN / 2;
    for (int i = 0; i < n; i++) {
        if (s[i] == c) prev = i;
        res[i] = i - prev;
    }
    prev = INT_MAX / 2;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == c) prev = i;
        res[i] = min(res[i], prev - i);
    }
    return res;
}

Key Takeaways

• Two directional passes capture the nearest target on each side.
• Initialise prev to infinity so untouched sides stay large.
• A clean example of the "scan from both directions" pointer idea.