Replace spaces with '%20'

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 
#include 
#include 
#include 
// 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;
}

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 
#include 
#include 

// 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);
}

StackExchange Code Review Q#117797, answer score: 6