Move the Spaces to Front of the String

Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place.
string = “move these spaces to beginning”
output =” movethesepacestobeginning”

Solution:

1) Maintain two indices i and j.
2) Traverse from end to beginning.
If the current index contains char, swap chars in index i with index j.
This will move all the spaces to beginning of the array.

Implementation:

#include<iostream>
using namespace std;
int main()
{
	char a[]="Move space to begining";
	int n=strlen(a)-1,count = n;

	//MoveSpace(a,0,strlen(a)-1);
	for(int i=n;i>=0;i--)
	{
		if(a[i] != ' ')
		a[count--] = a[i];
	}
	
	while(count>=0)
		a[count--] = ' ';
	cout << "After Space Moved to Begining" << a << endl;

	return 0;
}

Time Complexity: O(n) where n is the number of characters in input array.
Space Complexity: O(1).

3 Thoughts on “Move the Spaces to Front of the String

  1. Gajendra on October 14, 2013 at 8:39 pm said:

    Isn’t is same problem as moving all zeros to end or front in an array?

  2. Yes, it is same.
    Here it is changed a bit to make it faster.

  3. Shobhank on December 7, 2014 at 9:34 am said:

    public static String moveSpacesToFront(String in){
    int i = 0;
    while(i<in.length()){
    if(in.charAt(i) == ' '){
    in = in.substring(0, i) + in.substring(i+1, in.length());
    in = '_' + in;
    }
    i++;
    }
    return in;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation