Problem

Write a C program that will replace all spaces with ‘%20′

Examples

1
2

Input: s = "Mr John Smith"
Output: "Mr%20John%20Smith

Solution

Method 1 - Count spaces and traverse from end

The algorithm is as follows:

  1. Count the number of spaces during the first scan of the string.
  2. Parse the string again from the end and for each character:         If a space is encountered, store “%20”.         Else, store the character as it is in the newly shifted location.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void replaceSpaces(char[] str, int length) {
    int spaceCount = 0, newLength, i = 0;

    for (i = 0; i < length; i++) {
        if (str[i] == ' ') {
            spaceCount++;
        }
    }

    newLength = length + spaceCount * 2;
    str[newLength] = '\0';
    for (i = length - 1; i >= 0; i--) {
        if (str[i] == '') {
            str[newLength - 1] = '0';
            str[newLength - 2] = '2';
            str[newLength - 3] = '%';
            newLength = newLength - 3;

        } else {
            str[newLength - 1] = str[i];
            newLength = newLength - 1;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(1) - no extra space

Method 2 - Count spaces and traverse from end

Here we are traversing in forward direction. Here is a c code doing the similar stuff, borrowed from here.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

void replaceSpaces() {
    char src[] = "helo b";
    int len = 0, spaces = 0;
    /* Scan through src counting spaces and length at the same time */
    while (src[len]) {
        if (src[len] == ' ')
            ++spaces;
        ++len;
    }
    /* Figure out how much space the new string needs (including 0-term) and allocate it */
    int newLen = len + spaces * 2 + 1;
    char * dst = malloc(newLen);
    /* Scan through src and either copy chars or insert %20 in dst */
    int srcIndex = 0, dstIndex = 0;
    while (src[srcIndex]) {
        if (src[srcIndex] == ' ') {
            dst[dstIndex++] = '%';
            dst[dstIndex++] = '2';
            dst[dstIndex++] = '0';
            ++srcIndex;
        } else {
            dst[dstIndex++] = src[srcIndex++];
        }
    }
    dst[dstIndex] = '\0';
    /* Print the result */
    printf("New string: '%s'\n", dst);
    /* And clean up */
    free(dst);
    return 0;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(1) - no extra space