Replace Spaces
You have been given a string 'STR' of words. You need to replace all the spaces between words with “@40”.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain a single string 'STR' consisting of one or more words.

Output Format:

For each test case, return the modified string after replacing all the spaces between words with “@40”. Print the output of each test case in a separate line.

Note:

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Replace Spaces

You have been given a string 'STR' of words. You need to replace all the spaces between words with “@40”.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single string 'STR' consisting of one or more words.

Output Format:

For each test case, return the modified string after replacing all the spaces between words with “@40”.

Print the output of each test case in a separate line.

Note:

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
0 <= |STR| <= 100

Where ‘|STR|’ is the length of a particular string including spaces.

Time limit: 1 sec

Accepted Answer

One approach could be to calculate the number of spaces in the given string. Calculate the new length of the string as original length + 2*(number of spaces). Create a new string of the length calculated. Traverse the original string and keep appending all characters except spaces in the new string. As soon as a space is encountered, append '%20' in the string. Return the new string created.

Accepted Answer

Using Another String

The basic idea is to use a separate string to store the resultant string. Copy characters from the original string to the resultant string one by one, and whenever there comes a space, simply add “@40” in the resultant string in place of the space.

The steps are as follows:

Initialise a string let’s say 'RES, to store the resultant string.
Start traversing through the string one by one and do the following:
- If you come through space:
  - Add “@40” in place of space.
- If it is any other character:
  - Simply add the character.
Return the resultant string ‘RES’.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the string of words.

Since we are using an auxiliary string to store the resultant string of words, the space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the string of words.

Since we are traversing through the complete string of words only once, the time complexity is O(N).

C++ (g++ 5.4)

/*
	Time Complexity : O(N)
	Space Complexity : O(N)

	Where 'N' is size of string of words.
*/

string replaceSpaces(string &str){
	// String to store result.
	string res;
	
	// Variable to store length of string.
	int len = str.size();

	// Iterate the length of the string.
	for(int i = 0; i < len; i++){
		// Add "@40" in place of space.
		if(str[i] == ' '){
			res += "@40";
		}
		// Add character to result.
		else{
			res += str[i];
		}
	}
	// Return result.
	return res;
}

Python (3.5)

"""
	Time Complexity : O(N)
	Space Complexity : O(N)

	Where 'N' is size of string of words.
"""

def replaceSpaces(str):
	# String to store result.
	res = ""
	
	# Variable to store length of string.
	leng = len(str)

	#  Iterate the length of the string.
	for i in range(leng):
		# Add "@40" in place of space.
		if(str[i] == ' '):
			res += "@40"
		# Add character to result.
		else:
			res += str[i]
		
	# Return result.
	return res

Java (SE 1.8)

/*
	Time Complexity : O(N)
	Space Complexity : O(N)

	Where 'N' is size of string of words.
*/

public class Solution {
	public static StringBuilder replaceSpaces(StringBuilder str) {
		// To store result.
		StringBuilder res = new StringBuilder();

		// Variable to store length.
		int len = str.length();

		// Iterate the length of the string.
		for (int i = 0; i < len; i++) {
			// Add "@40" in place of space.
			if (str.charAt(i) == ' ') {
				res.append("@40");
			}
			// Add character to result.
			else {
				res.append(str.charAt(i));
			}
		}
		// Return result.
		return res;
	}
}

Accepted Answer

In-place manipulation

The basic idea of this approach is to assume that string have extra space in the input string.

For example:

S: “Coding Ninjas “

Extra space, in the end, can be used to add @40 in the string

Output: Coding@40Ninjas

In this approach, we will be counting the number of spaces in the string and then calculate the length of the resultant string using that count.

For example:

S: “Coding Ninjas“

‘SPACECOUNT’ = 1

Length of resultant string: (length of string) + ‘SPACECOUNT’ * 2 - 1

Now start replacing spaces from the end with “@40”

String updated

The steps are as follows:

Count spaces and find the current length
Remove the trailing spaces
Find the new length using:
- new length: length + ‘SPACECOUNT’ * 2 - 1
Start filling character from the end
Insert “@40”, in place of space
Return the string.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the size of the string of words.

Since we are traversing through the complete string of words linearly, the time complexity is O(N).

Java (SE 1.8)

/*
	Time Complexity : O(N)
	Space Complexity : O(1)

	Where 'N' is size of string of words.
*/

public class Solution {
	public static StringBuilder replaceSpaces(StringBuilder str) {
		int spaceCount = 0;

		// Count Number of Spaces.
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == ' ') {
				spaceCount = spaceCount + 1;
			}
		}

		// Store thr current length of the string in a variable.
		int len = str.length();

		// Find the new length.
		int newLength;
		newLength = len + (spaceCount * 2);

		// Resize the current string.
		int oldLength = str.length();
		for (int i = 0; i < newLength - oldLength; i++) {
			str.append(' ');
		}

		// Index to end of string.
		int index = newLength - 1;

		// Fill string from end.
		for (int k = len - 1; k >= 0; k--) {
			if (str.charAt(k) == ' ') {
				str.setCharAt(index, '0');
				str.setCharAt(index - 1, '4');
				str.setCharAt(index - 2, '@');
				index = index - 3;
			} 
			else {
				str.setCharAt(index, str.charAt(k));
				index = index - 1;
			}
		}
		// Return string.
		return str;
	}
}

Python (3.5)

"""
	Time Complexity : O(N)
	Space Complexity : O(N) 
	(Because string in python is immutable and so we need to use a separate string).

	Where 'N' is size of string of words.
"""

def replaceSpaces(str):
	spaceCount = 0
	
	# Count Number of Spaces.
	for i in range(len(str)):
		if(str[i] == ' '):
			spaceCount = spaceCount + 1

	# Store thr current length of the string in a variable.
	leng = len(str)
	
	# Find the new length.
	newLength = leng + (spaceCount * 2)
	
	# Resize the current string.
	temp = newLength - leng
	for i in range(temp):
		str += ' '
	
	# Index to end of string.
	index = newLength - 1
	
	l = []
	for i in range(leng):
		l.append(i)
	l.reverse()

	str = list(str)
	# Fill string from end.
	for k in l:
		if(str[k] == ' '):
			str[index] = '0'
			str[index - 1] = '4'
			str[index - 2] = '@'
			index = index - 3
		else:
			str[index] = str[k]
			index = index - 1

	answer = ""
	for x in str:
		answer += x
		
	# Return string.
	return answer

C++ (g++ 5.4)

/*
	Time Complexity : O(N)
	Space Complexity : O(1)

	Where 'N' is size of string of words.
*/

string replaceSpaces(string &str){
	int spaceCount = 0;
	
	// Count Number of Spaces.
	for(int i = 0; i < str.size(); i++){
		if(str[i] == ' '){
			spaceCount = spaceCount + 1;
		}
	}

	// Store thr current length of the string in a variable.
	int len = str.size();
	
	// Find the new length.
	int newLength;
	newLength = len + (spaceCount * 2);
	
	// Resize the current string.
	str.resize(newLength);
	
	// Index to end of string.
	int index = newLength - 1;
	
	// Fill string from end.
	for(int k = len - 1 ; k >= 0; k--){
		if(str[k] == ' '){
			str[index] = '0';
            str[index - 1] = '4';
            str[index - 2] = '@';
            index = index - 3;
		}
		else{
			str[index] = str[k];
			index = index - 1;
		}
	}	
	// Return string.
	return str;	
}

You have been given a string 'STR' of words. You need to replace all the spaces between words with “@40”.

Input Format:

Output Format:

Note:

Constraints:

Top Housing.com Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Housing.com Software Developer