Shortest Distance to a Character(#821)
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
### Key Idea
• First, collect all the indices where the character `c` appears and store them in an array `cIndexes`.
• Then traverse the string `s`, and for each character, compute the closest distance to any of the indices in `cIndexes`.
• Use a pointer `index` to keep track of the closest positions in `cIndexes`.
• If current index is before or at `cIndexes[index]`, use that.
• If it's after, check which of `cIndexes[index]` or `cIndexes[index + 1]` is closer and update accordingly.
This avoids brute force and leverages an efficient two-pointer technique.
💻 Code
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.