Shortest Distance to a Character
(#821), Easy
Category: Array, Two Pointer, String
Problem Statement
You're given a string `s` and a character `c` that is guaranteed to occur at least once in `s`. Your task is to return an array of integers — where each element represents the shortest distance from the corresponding character in the string to the nearest occurrence of `c`. Distance is the absolute difference between indices.
Examples
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Input: s = "aaab", c = "b"
Output: [3,2,1,0]
Approach
Efficient Two-Pointer Strategy
- First, collect all indices where character `c` appears into an array `cIndexes`.
- Initialize a pointer `index = 0` to track the nearest `c` as you iterate.
- Loop through each character of `s` and for each index `i`:
- - If `i` is before or equal to `cIndexes[index]`, compute distance as `|i - cIndexes[index]|`.
- - If `i` is past `cIndexes[index]`, compare `|i - cIndexes[index]|` and `|i - cIndexes[index+1]|` (if it exists), then use the closer one.
- Store each computed distance in a result array.
- Return the final distance array after the loop ends.
let cIndexes = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === c) {
cIndexes.push(i);
}
}
let distance = [];
let index = 0;
for (let i = 0; i < s.length; i++) {
if (i <= cIndexes[index]) {
let dist = Math.abs(i - cIndexes[index]);
distance.push(dist);
} else {
if (index + 1 < cIndexes.length) {
let dist1 = Math.abs(i - cIndexes[index]);
let dist2 = Math.abs(i - cIndexes[index + 1]);
if (dist2 < dist1) {
index++;
distance.push(dist2);
} else {
distance.push(dist1);
}
} else {
let dist = Math.abs(i - cIndexes[index]);
distance.push(dist);
}
}
}
return distance;Complexity
Time: O(n) — One pass to gather indices, one pass to calculate distances.
Space: O(n) — To store both `cIndexes` and the `distance` result array.