Replace all spaces in a string with %20

Problem Statement

Replace all spaces in a string with ‘%20’ (three characters). Do this in place and assume you have enough space in array

Solution (Simple)

This is the simplest solution which many people might think.

Iterate from left side (begining)
After encountering a space, first shift entire array by 2 places.
Put %20 at consecutive location
Repeat this process

Obviously, if you see you need to shift the remaining array as many times as number of spaces. And, is not an efficient algorithm.

I will not put this silly code.

Complexity

The complexity would be close to O(n^2)

A Better Solution

If you start from left side, you saw we need to shift the array. What if we start from the right side.

First calculate number of spaces in array, this will help in calculating the resultant last index
Start iterating from right most side.
Maintain two index counters. One for original array characters, other for resultant index positions.
Start copying character one by one.
If found space, just copy consecutive %20

At the end, you will achieve the purpose. Lets see the code

private static int countSpaces(char[] input) {
   int c = 0;
   for (int i=0; i<input.length; i++) {
      if (input[i] == ' ') {
         c ++;
      }
   }
   return c;
}

public static int replace(char[] input, int len) {
   int spaces = countSpaces(input);
   if (spaces == 0) return len;
   
   int lastIndex = (len-1) + (2 * spaces);
   int resultIndex = lastIndex;
   
   for (int i=len-1; i>=0; i--) {
      if (input[i] == ' ') {
         //copy %20
         input[lastIndex] = '0';
         input[lastIndex-1] = '2';
         input[lastIndex-2] = '%';
         lastIndex -= 3;
      }
      else {
         //copy actual characters
         input[lastIndex] = input[i];
         lastIndex --;
      }
   }
   
   return resultIndex;
}