DEV Community

Sahil Bondre
Sahil Bondre

Posted on

3 1

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"
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Image of Datadog

Master Mobile Monitoring for iOS Apps

Monitor your app’s health with real-time insights into crash-free rates, start times, and more. Optimize performance and prevent user churn by addressing critical issues like app hangs, and ANRs. Learn how to keep your iOS app running smoothly across all devices by downloading this eBook.

Get The eBook

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more