Description:
Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.
The distance between two indices i and j is abs(i - j), where abs is the absolute value function.
Solution:
Time Complexity : O(n)
Space Complexity: O(n)
// Scan twice, one time starting at the front and another starting at the back
// Populate the answer array with Infinity as a place holder until we find an index of 'c'
// Find the distance between the current index and the previous index of 'c'
// The final 'ans' array will be populated with the smallest difference found at each position between the two approaches of scanning from the front and scanning from the back
var shortestToChar = function(s, c) {
const N = s.length;
const ans = new Array(N);
let prev = -Infinity;
// Populate difference from starting from the front
for (let i = 0; i < N; ++i) {
if (s[i] === c) prev = i;
ans[i] = i - prev;
}
// Populate the 'ans' array with the min difference between starting from the front and starting from the back
prev = Infinity;
for (let i = N-1; i >= 0; --i) {
if (s[i] === c) prev = i;
ans[i] = Math.min(ans[i], prev - i);
}
return ans;
};
Top comments (0)