Shortest Distance to a Character
Problem
Given a string s and a character c that appears in s, return an array of integers where answer[i] is the distance from index i to the closest occurrence of c in s.
s = "loveleetcode", c = "e"[3,2,1,0,1,0,0,1,2,2,1,0]def shortestToChar(s, c):
n = len(s)
res = [n] * n
prev = -n
for i in range(n):
if s[i] == c: prev = i
res[i] = i - prev
prev = 2 * n
for i in range(n - 1, -1, -1):
if s[i] == c: prev = i
res[i] = min(res[i], prev - i)
return res
function shortestToChar(s, c) {
const n = s.length;
const res = new Array(n).fill(n);
let prev = -n;
for (let i = 0; i < n; i++) {
if (s[i] === c) prev = i;
res[i] = i - prev;
}
prev = 2 * n;
for (let i = n - 1; i >= 0; i--) {
if (s[i] === c) prev = i;
res[i] = Math.min(res[i], prev - i);
}
return res;
}
class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] res = new int[n];
int prev = -n;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == c) prev = i;
res[i] = i - prev;
}
prev = 2 * n;
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;
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n = s.size();
vector<int> res(n, n);
int prev = -n;
for (int i = 0; i < n; i++) {
if (s[i] == c) prev = i;
res[i] = i - prev;
}
prev = 2 * n;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == c) prev = i;
res[i] = min(res[i], prev - i);
}
return res;
}
};
Explanation
For each position we want the distance to the nearest target character c, and that nearest c could be either on the left or on the right. The neat solution makes two passes — one each direction — and keeps the smaller distance.
In the left-to-right pass, we remember prev, the index of the most recent c seen so far. For each i, the distance to a c on the left is simply i - prev. We start prev as a far-away value so positions before the first c get a large number.
In the right-to-left pass, we again track the nearest c, now coming from the right, and update each answer with min(res[i], prev - i). Taking the minimum of both passes gives the true closest c in either direction.
Example: s = "loveleetcode", c = "e". The forward pass measures distance to the previous e, the backward pass to the next e, and combining them yields [3,2,1,0,1,0,0,1,2,2,1,0].
Two linear sweeps mean the whole thing is O(n) time, using one result array for output.