Interview Prep #4: URLify String

Problem

Whenever data is sent as a URL, spaces are replaced by %20. In this problem we are given a piece of text and we are supposed to URLify it. Wherever we encounter space we should replace it by the %20.

Notice that when we replace a space by a %20, we are taking up two more characters. In this problem we are given the text as a string followed by a bunch of spaces so that we have enough space to URLify the string. Additionally we are also provided with the length of original text in the string.

Example:

Input: "pan cakes  ", 9 
(The text is "pan cakes" followed by two spaces to accommodate the "%20")

Output: "pan%20cakes"

Solution

In most of the string editing problems it's a good idea to start from behind and work our towards the start of the string. We will first estimate number of spaces in the text. Then we'll use two pointers to edit the string from behind.

The first pointer will be at the end of the actual text and second pointer will be the end of the string. We'll then work our way backwards. If the first pointer finds a space we will make the %20 string at the position of second pointer. Then the second pointer will be reduced by 3 and first by one. If the first pointer runs across a not space, we will just move the character from the first pointer to the second pointer position.

If this sounds confusing, it is fine. I think its one of those problems where the explanation is more confusing than the actual algorithm. Try reading the code and rewriting it yourself to get a hang of it.

string urlify_string(string& s, int true_length) {
  // find number of spaces
  int space_count = 0;
  for (auto i = 0; i < true_length; ++i) {
    if (s[i] == ' ') {
      ++space_count;
    }
  }

  // second counter
  int final_index = true_length + 2 * space_count;
  // i is the first counter
  for (auto i = true_length - 1; i >= 0; --i) {
    if (s[i] == ' ') {
      s[final_index - 1] = '0';
      s[final_index - 2] = '2';
      s[final_index - 3] = '%';
      final_index -= 3;
    } else {
      s[final_index - 1] = s[i];
      --final_index;
    }
  }
  return s;
}

References: Cracking the Coding Interview - Gayle Laakmann McDowell
Have a marvelous day 😄