# Write a method to replace all spaces in a string with ‘%20’

QUESTION:

URLify: 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. (Note: if implementing in Java, please use a character array so that you can perform this operation in place).

EXAMPLE:
Input: “Mr John Smith “, 13
Output: “Mr%20John%20Smith”

SOLUTION:

• A common approach in string manipulation problems is to edit the string starting from the end and working backwards.
• This is useful because we have an extra buffer at the end, which allows us to change characters without worrying about what we’re overwriting.
• We will use this approach in this problem. The algorithm employs a two-scan approach.
• In the first scan, we count the number of spaces. By tripling this number, we can compute how many extra characters we will have in the final string.
• In the second pass, which is done in reverse order, we actually edit the string.
• When we see a space, we replace it with %20. If there is no space, then we copy the original character.

The code below implements this algorithm.

```void  replaceSpaces(char[]  str,  int trueLength  )  {
int spaceCount = 0, index, i = 0;
for (i - 0; i < trueLength; i++) {
itf  (str[i] ==  '  ')  {
spaceCount++;
}
}

index = trueLength + spaceCount * 2;
if (truelength < str.length) str[trueLength] = '\0'; // End  array
for (i = truelength - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[index 1] '0';
str[index - 2] = '2';
str[index - 3] = '%';
index = index - 3;
} else {
str[index - 1] = str[i];
index--;
}
}
}```
• We have implemented this problem using character arrays, because Java strings are immutable.
• If we used strings directly, the function would have to return a new copy of the string, but it would allow us to implement this in just one pass.