Replace spaces with '%20'

Question

This is my attempted solution to Question 1.3 from "Cracking the Code Interview", 6th ed.

Question:

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.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
// Input:  "Mr John Smith    ", 13
// Output: "Mr%20John%20Smith"

int countSpaces(char* str) {
  int i = 0, j = 0;
  while (str[i] != '\0')
    if ( str[i++] == ' ')
      j++;

  return j;
}

char* replaceChars(char* str, int length) {
  int x = countSpaces(str);
  int stringLength = length + x - x/3;

  char* urlifiedString = malloc((stringLength + 1) * sizeof(char));
  int i = 0, j = 0;
  while (i < stringLength) {
    if (str[j] != ' ') {
      urlifiedString[i++] = str[j];
    } else if (str[j] == ' '){
      urlifiedString[i++] = '%';
      urlifiedString[i++] = '2';
      urlifiedString[i++] = '0';
    }
    j++;
  }
  urlifiedString[stringLength] = '\0';
  return urlifiedString;
}

int main() {
  char* result1 = replaceChars("Mr John Smith    ", 13);
  printf("%s\n", result1);
  printf("%li\n", strlen(result1));
  assert(strcmp("Mr%20John%20Smith", result1) == 0);
  free(result1);

  char* result2 = replaceChars("lol  lol lol      ", 12);
  printf("%s\n", result2);
  assert(strcmp("lol%20%20lol%20lol", result2) == 0);
  free(result2);

  char* result3 = replaceChars("", 0);
  assert(strcmp("", result3) == 0);
  free(result3);

  return 0;
}

Answer 1

I think you have misunderstood the part about "assume that the string has sufficient space at the end", and as a result, you have some memory management issues. I think that the intention is to assure you that your replaceChars() function will be handed a buffer of sufficient size such that you may write the result in place, without allocating more memory.

In that light, your solution and tests look a bit confused — and in fact the code is wrong in the general case. If the input is "Mr␠John␠Smith␠␠␠␠", and you countSpaces() without taking the true length (13) into account, then countSpaces() would report that there are 6 spaces rather than 2. To compensate for the overestimate, you then use the formula int stringLength = length + x - x/3; — allocating roughly \$\frac{2}{3}\$ of an additional byte for each space, rather than two extra bytes per space. And you are also relying on that dubious estimate of the result length to terminate your loop, with while (i < stringLength).

Suggested solution

#include <stdlib.h>
#include <assert.h>
#include <string.h>

// Count the spaces in the first n bytes of str
int countSpaces(const char* str, int n) {
  int count = 0;
  while (n --> 0) {
    if (*str++ == ' ') {
      count++;
    }
  }
  return count;
}

char* replaceChars(char* str, int length) {
  int spaces = countSpaces(str, length);
  char *in = str + length - 1,
       *out = str + length + 2 * spaces;
  *out-- = '\0';
  while (in != out) {
    if (*in == ' ') {
      out -= 3;
      in--;
      *(out + 1) = '%';
      *(out + 2) = '2';
      *(out + 3) = '0';
    } else {
      *out-- = *in--;
    }
  }
  return str;
}

int main() {
  const char *test1 = "Mr John Smith";
  char buf1[18] = {0};
  strcpy(buf1, test1);
  replaceChars(buf1, strlen(test1));
  assert(strcmp("Mr%20John%20Smith", buf1) == 0);

  const char *test2 = "lol  lol lol";
  char buf2[19] = {0};
  strcpy(buf2, test2);
  replaceChars(buf2, strlen(test2));
  assert(strcmp("lol%20%20lol%20lol", buf2) == 0);

  const char *test3 = "";
  char buf3[1] = {0};
  strcpy(buf3, test3);
  replaceChars(buf3, strlen(test3));
  assert(strcmp("", buf3) == 0);
}

Answer 2

Here are some things that may help you improve your code.

Read the problem statement carefully

The problem says that you're to replace all spaces and that:

You may assume that the string has sufficient space at the end to hold the additional characters

This strongly suggests that the intent is to have the code operate on the string in place rather than making a duplicate string as your current code does.

Use const where practical

Your countSpaces routine does not (and should not) alter the passed char *, so the declaration should instead be this:

int countSpaces(const char* str) 

Consider signed versus unsigned

(Thanks to @Lundin for mentioning this in a comment.) Is the length of a string ever going to be negative? Is the number of spaces ever going to be negative? If not, then both of those should probably be declared as unsigned rather than int.

Use more descriptive variable names

Names such as result1 are good, but names like i and j are not very descriptive. Generally, it's better to only use i and j for loop variables.

Use braces for control structures

Code like this:

while (str[i] != '\0')
    if ( str[i++] == ' ')
        j++;

is a maintenance accident waiting to happen. If someone adds a line to it, perhaps for debugging or diagnostics, it will break unless they also add braces. Better is to use braces always, especially if you are just beginning.

Use pointers effectively

One thing that skilled C programmers do is use pointers effectively. It's often faster than the equivalent code that uses array indexing and is also frequently shorter as well. As an example, the current code contains this:

int countSpaces(const char* str) {
  int i = 0, j = 0;
  while (str[i] != '\0')
    if ( str[i++] == ' ')
      j++;

  return j;
}

This could be rewritten using a pointer like so:

unsigned countSpaces(const char* str, unsigned len) {
  unsigned count;
  for(count = 0; len; --len) {
    if (*str++ == ' ') {
        ++count;
    }
  }
  return count;
}

Note, too that the rewritten code uses a more descriptive variable name and braces ({}) for each control structure. Adding braces makes the code less error prone to maintain.

Answer 3

Your code looks good - it seems to do the job you want it to. The only thing is where you use malloc((stringLength + 1) * sizeof(char)); you want to make it convert to type char*. Just throw it out like:

char* urlifiedString = (char*)malloc((stringlength + 1) * sizeof(char));

Also, once you free result1, just point it to new information with a malloc(). You don't need to make a second or third character pointer to assign new stuff to. The only thing you don't want to do is free(somepointer) if there isn't any memory reserved for the pointer.

Good job!