# Replace all spaces in a string with %20

October 01, 2020

## 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;
}``````

### Complexity

The complexity is `O(n)`

## Similar Posts

### Three Sum - Leet Code Solution

Problem Statement Given an array nums of n integers, are there elements a, b, c…

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

### Leetcode - Rearrange Spaces Between Words

Problem Statement You are given a string text of words that are placed among…

### Maximum Length of Subarray With Positive Product - Leet Code Solution

Problem Statement Maximum Length of Subarray With Positive Product. Given an…

### Leetcode - Maximum Non Negative Product in a Matrix

Problem Statement You are given a rows x cols matrix grid. Initially, you are…

### Find if Array contains Duplicate Number - Leet Code Solution

Problem Statement Given an array of integers, find if the array contains any…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…