## Saturday, January 18, 2014

### Problem

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

Example
Input:              "Mr John Smith    "
Output:            "Mr%20John%20Smith

### Solution

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.
Java code
```public static void ReplaceFun(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;
}
}
}
```

Time Complexity: O(N), N is length of the string.

C code
Here is a c code doing the similar stuff, borrowed from here :
```int main() {
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;
}
```

Point to note here is that when you are using malloc, set the last index to '\0' as it is a c-style string OR you can use calloc.