Cracking the Coding Interview: URLify

2023-09-26

• 2 min read

#javascript #algorithms_and_data_structures

This post is part of the Algorithms Problem Solving series and a problem from the Cracking the Coding Interview book.

Problem description

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string

Examples

input: 'Mr John Smith     ', 13
output: 'Mr%20John%20Smith'

input: 'Mr John Smith     ', 13
output: 'Mr%20John%20Smith'

Solutions

The first solution we go through the characters one by one until we reach the length input.

If it's not a space character, we just add it to the output array. If it's a space character and the last character was not a space character, we add the placeholder %20.

We check the last character because we want to add the placeholder only one time even if we have consecutive spaces.

In the end, we have the new string in an array format, so we just need to join all the characters, form the string, and return it.

Runtime Complexity: O(N), where N = the true length of the string
Space Complexity: O(N), where N = the true length of the string in the new array

function urlify(string, length, placeholder = '%20') {
  let output = [];
  let lastChar = '';
  let space = ' ';

  for (let index = 0; index < length; index++) {
    let char = string[index];

    if (char !== space) {
      output.push(char);
    }

    if (char === space && lastChar !== space) {
      output.push(placeholder);
    }

    lastChar = char;
  }

  return output.join('');
}

The second solution is similar but instead of having a lastChar variable, we move the index forward when it reaches the first space.

If the character is a space, we add the placeholder %20 to the output array and move forward the index until it finishes all consecutive spaces. If it's not a space character, we just add it to the output array.

Runtime Complexity: O(N), where N = the true length of the string
Space Complexity: O(N), where N = the true length of the string in the new array

function urlifyForward(string, length, placeholder = '%20') {
  let output = [];
  let index = 0;
  let space = ' ';

  const moveForward = () => {
    while (string[index] === space) {
      index++;
    }
  };

  while (index < length) {
    if (string[index] === space) {
      output.push(placeholder);
      moveForward();
    } else {
      output.push(string[index]);
      index++;
    }
  }

  return output.join('');
}

Resources

Twitter Github