Replace all spaces in a string by %20. Amazon Interview

Replace all spaces in a string by %20.

Amazon Interview (Jan 2012)

Problem Statement

Replace all spaces in a string by %20. Write production quality code in first attempt  

Algorithm

1) Move along the string and count no of spaces.

2) New string length would be old string length + 2*no of spaces.

3) Start transferring characters from old string to new string and where ever there is space replace it with %20 as asked in question else transfer character as it is to new string. 

4) Finally put a '\0' character in end  of the new string.

Solution

// Replace all spaces in a string by %20.
// Write production quality code in first attempt.

#include<stdio.h>
#include<string.h>

int main()
{

char str[100];
//syntax to scan string till new line in C
scanf("%[^\n]", str);

int len = strlen(str);
int i,count=0,k=0;
for(i=0;i<len;i++)
    if(str[i]==' ') count++;
   
char newstr[len+2*count];
for(i=0;i<len;i++)
{
    if(str[i]==' ') {
        newstr[k++] = '%';
        newstr[k++] = '2';
        newstr[k++] = '0';
    }
    else
        newstr[k++] = str[i];
}
newstr[k] = '\0';
printf("%s\n", newstr);

}

Time Complexity

O(2n) <==> O(n) since we move pointer along string twice.