# Find The Shortest Distance To A Character

04/19/22

## Intro

For this algorithm, we are given a string `s` and a character `c`. For every character in `s` you must find the shortest distance from that character to `c`. When finished, you should return your answer as an array of integers.

For example, let's say we have `s = 'freezing'` and `c = 'e'`. The array that we return should be `[2, 1, 0, 0, 1, 2, 3, 4]`. It is important to note that this solution requires that you traverse `s` backwards, as well as forwards. This will make more sense when we start writing some code.

## Creating A Basic Function

To get started, let's create a basic function.

``````/**
* @param {string} s
* @param {character} c
* @return {number[]}
*/
const shortestDistance = (s, c) => {
const arr = []

for(let i = 0; i < s.length; i++) {
// do stuff here...
}
}
``````

I've added a few things to save on time. First is `arr`, which we will fill up over time and eventually return as our answer. Also, I've created a basic `for loop`, as it is obvious that we need to iterate through `s`. From here, we can start figuring out the most important parts of our algorithm.

## Two Pointers And A While Loop.

Our premise is simple, for every character in `s`, traverse forward and backward from that character in `s` at the same time. To do this, we can make use of a while loop with two pointers. On top of that we will also add another variable named `hasFound`.

``````/**
* @param {string} s
* @param {character} c
* @return {number[]}
*/
const shortestDistance = (s, c) => {
const arr = []

for(let i = 0; i < s.length; i++) {
let hasFound = false
let left = i - 1;
let right = i + 1

while(!hasFound) {
// do stuff here
}
}
}
``````

From here we need to check a few cases inside our while loop:

1. If the current character is the same as `c`.
2. If the character to the left of the current number is equal to `c`.
3. If the character to the right of the current number is equal to `c`.
4. If neither character to the left or right of the current character is equal to `c`.

If we meet the requirements of the first case, then we will add 0 to the `arr` and exit the while loop. Same goes for steps 2 and 3, except we also need to use a little bit of math to figure out how far the character is. For step 4, all that's needed is to decrement `left` and increment `right`, and continue the while loop.

After we've looped through all characters in `s` we can return `arr`, which will be full of integers.

``````/**
* @param {string} s
* @param {character} c
* @return {number[]}
*/
const shortestDistance = (s, c) => {
const arr = []

for(let i = 0; i < s.length; i++) {
let hasFound = false
let left = i - 1;
let right = i + 1

while(!hasFound) {
if(s[i] === c) {
arr.push(0)
hasFound = true
} else if(s[left] === c) {
const distance = Math.abs(i - left)
arr.push(distance)
hasFound = true
} else if(s[right] === c) {
const distance = Math.abs(i - right)
arr.push(distance)
hasFound = true
} else {
left--
right++
}
}
}

return arr
}
``````

## Summary

If you have any problems understanding any of this, feel free to shoot me a message, and I'll make sure it's crystal clear.