The following solution uses no extra space and runs in O(n) time. The trick here is to start copying the characters from the end, and wherever we find space replace it with '%20'. The following C++ code does exactly that.

#include <iostream> #define MAX 100 using namespace std; void replaceSpace(char *array) { int len=0,i; int spaceCount = 0; //this loop calculates the spaces and length of the string for( i = 0 ; array[i] != '\0' ; i++ ) { //count spaces if( array[i] == ' ') spaceCount++; //update length len++; } //array has enough space, try to copy the string from end //end index will be length + 2*no of spaces bcoz for each space //there will be (3-1=2) two additional characters inserted int resInd = len + 2*spaceCount; //len is the index of '\0' (i.e last) in the original string //start copying from there while ( len >= 0) { //if space, insert %20 in reverse, bcoz we are copying from reverse if( array[len] == ' ') { array[resInd--] = '0'; array[resInd--] = '2'; array[resInd--] = '%'; } else //copy as it is { array[resInd--] = array[len]; } len--; } } int main() { char chArray[MAX]; gets(chArray); replaceSpace(chArray); cout<<chArray<<endl; return 0; }