Given a string of characters consisting of 0 or more spaces, remove all the spaces from this given string. Separation of spaces from other characters should be done in-place(without using extra space). Expected time complexity is O(n).
For example, if the input string is " Hi, How are you? " then the output returned should be "Hi,Howareyou?"
Video coming soon!
Subscribe for more updates
Algorithm/Insights
For a given string, if there are 'j' number of spaces to the left of the character at index 'i', then that 'i'th character would be placed at (i-j)th index after removing all spaces from the given string.
Using above idea, all we do is traverse the given string from the leftmost character and keep counting the number of spaces seen so far. If the current character at index 'i' is a non-space character and if there are 'j' number of spaces seen so far then we copy 'i'th character to index (i-j). Note that because we are traversing this string from the leftmost end, character at index (i-j) would already have been placed in its correct position and therefore we don't need to worry about overwriting it. Following example should help you to visualize this step.
After the traversal of complete string, we would have counted the total number of spaces in the given string, let that be 'numSpaces'. Now all we do is remove the last 'numSpaces' characters of this string by copying characters of this modified string from index 0 to index (lengthOfString - numSpaces - 1) including both extremes into a new string. You can refer to function 'removeSpaces(String str)' for implementation details.
Please note that in the Java programming language, unlike C, an array of char is not a String, and neither a String nor an array of char is terminated by '\u0000' (the NUL character). Reference: https://docs.oracle.com/javase/specs/jls/se7/html/jls-10.html#jls-10.9 . Therefore we have to copy the modified string into a new string which would take O(n) extra space.
Please add comments in case you have any queries/feedback.
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.
Thanks, -Team IDeserve
Algorithm Visualization
Code Snippet
package com.ideserve.nilesh.questions;
import java.util.Arrays;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* Removes spaces from a given string in O(n) time.
* @author Nilesh
*/
public class RemoveSpaces
{
// removes spaces from given string
public static String removeSpaces(String str)
{
char[] charArray = str.toCharArray();
int numSpaces = 0; // number of spaces before 'i'th character
for (int i = 0; i < charArray.length; i++)
{
// count number of spaces
if (charArray[i] == ' ')
{
numSpaces += 1;
}
// put 'i'th character into its correct position after removing spaces before it
else
{
charArray[i-numSpaces] = charArray[i];
}
}
// all the spaces are moved towards the end of the string.
// Create new string by using non-space characters
charArray = Arrays.copyOf(charArray, charArray.length - numSpaces);
return new String(charArray);
}
public static void main(String[] args)
{
String strWithSpaces = " Hi there, how are you doing? ";
String strWithoutSpaces = removeSpaces(strWithSpaces);
System.out.println(strWithoutSpaces);
}
}
Order of the Algorithm
Time Complexity is O(n) Space Complexity is O(n)
Contribution
Sincere thanks from IDeserve community to Nilesh More for compiling current post.
Nilesh More
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.