Code Implementation

class Solution:
    def shortestToChar(self, s: str, c: str) -> list[int]:
        n = len(s)
        answer = [0] * n
        prev = float('-inf')
        # Left to right
        for i in range(n):
            if s[i] == c:
                prev = i
            answer[i] = i - prev if prev != float('-inf') else float('inf')
        # Right to left
        prev = float('inf')
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                prev = i
            answer[i] = min(answer[i], abs(prev - i))
        return answer
      

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        vector<int> answer(n, 0);
        int prev = -n;
        // Left to right
        for (int i = 0; i < n; ++i) {
            if (s[i] == c) prev = i;
            answer[i] = i - prev;
        }
        // Right to left
        prev = 2 * n;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == c) prev = i;
            answer[i] = min(answer[i], abs(prev - i));
        }
        return answer;
    }
};
      

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] answer = new int[n];
        int prev = Integer.MIN_VALUE / 2;
        // Left to right
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == c) prev = i;
            answer[i] = i - prev;
        }
        // Right to left
        prev = Integer.MAX_VALUE / 2;
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == c) prev = i;
            answer[i] = Math.min(answer[i], Math.abs(prev - i));
        }
        return answer;
    }
}
      

var shortestToChar = function(s, c) {
    const n = s.length;
    const answer = new Array(n);
    let prev = -Number.MAX_SAFE_INTEGER;
    // Left to right
    for (let i = 0; i < n; ++i) {
        if (s[i] === c) prev = i;
        answer[i] = i - prev;
    }
    // Right to left
    prev = Number.MAX_SAFE_INTEGER;
    for (let i = n - 1; i >= 0; --i) {
        if (s[i] === c) prev = i;
        answer[i] = Math.min(answer[i], Math.abs(prev - i));
    }
    return answer;
};
      

Problem Description

You are given a string s and a character c that occurs at least once in s. For each index i in s, you must determine the shortest distance from i to any occurrence of character c in s. The distance is the absolute difference of indices.

• Input: A string s and a character c (guaranteed to appear in s at least once).
• Output: An array of integers, where the ith element is the shortest distance from index i to any occurrence of c in s.
• Constraints: c occurs at least once; distances are based on absolute index difference; all positions in s must be considered.

Thought Process

To solve this problem, the most direct approach is to, for each index in the string, scan the entire string to find all positions of c and calculate the shortest distance. However, this brute-force method is inefficient, especially for long strings, since it repeats a lot of unnecessary work.

To optimize, we can recognize that the distance to the closest c for each index can be determined efficiently by scanning the string twice:

• First, scan from left to right, keeping track of the last position where c appeared. For each index, the distance to the last seen c is easy to compute.
• Then, scan from right to left, keeping track of the next position where c appears. For each index, the distance to the next c is also easy to compute.
• For each index, the minimum of these two distances is the answer.

This approach avoids redundant computation and ensures that each character in the string is only visited a constant number of times.

Solution Approach

Here is a step-by-step breakdown of the optimized algorithm:

1. Initialize Output Array: Create an array answer of the same length as s to store the result for each index.
2. First Pass (Left to Right):
   • Keep a variable prev to remember the most recent index where c was found. Initialize it to a very small number (or negative infinity) so the distance is large before the first c is seen.
   • For each index i from 0 to n-1:
     • If s[i] is c, update prev to i.
     • Set answer[i] to the distance from i to prev (i.e., i - prev).
3. Second Pass (Right to Left):
   • Reset prev to a very large number (or positive infinity).
   • For each index i from n-1 down to 0:
     • If s[i] is c, update prev to i.
     • Set answer[i] to the minimum of its current value and the distance to prev (i.e., abs(prev - i)).
4. Return the Result: After both passes, answer contains the shortest distances for all indices.

This two-pass method ensures that each position's answer reflects the nearest occurrence of c on either side.

Example Walkthrough

Let's use the string s = "loveleetcode" and c = 'e' as an example.

• Indices of e: 3, 5, 6, 11

First pass (left to right):
We track the last seen e and fill in distances. Before index 3, no e has been seen, so the distance is large.
At index 3, e is found, so distance is 0. For subsequent indices, distance increases until another e is found.

Second pass (right to left):
We track the next e from the right. For each index, we take the minimum of current value and distance to the next e.

Final output:
The resulting array is [3,2,1,0,1,0,0,1,2,2,1,0], representing the shortest distance to an e for each character in "loveleetcode".

Time and Space Complexity

• Brute-force approach:
  • For each index, scan the entire string to find the closest c: O(n^2) time.
  • Space: O(n) for the output array.
• Optimized two-pass approach:
  • Each pass is O(n), so total time is O(n).
  • Space: O(n) for the output array, and O(1) extra space for variables.

The optimized approach is much faster and suitable for large strings.

Summary

The key insight is to avoid repetitive scanning by using two linear passes: one from the left and one from the right, each tracking the most recent occurrence of the target character. This guarantees that each index gets the minimum possible distance efficiently. The solution is elegant because it leverages simple state tracking and only needs to look at each character a constant number of times.