Find The Shortest Distance To A Character

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.