Given a string that has set of words and spaces, write a program to move all spaces to front of string, by traversing the string only once.
Input : str = "Beginner for Beginner"
Output : str = " w3wiki"
Input : str = "move these spaces to beginning"
Output : str = " movethesespacestobeginning"
There were four space characters in input,
all of them should be shifted in front.
Method 1 (Using Swap): Idea is to maintain two indices i and j. Traverse from end to beginning. If the current index contains space, swap chars in index i with index j. This will bring all spaces to beginning of the array.
C++
#include<bits/stdc++.h>
using namespace std;
void moveSpaceInFront( char str[])
{
int i = strlen (str)-1;
for ( int j = i; j >= 0; j--)
if (str[j] != ' ' )
swap(str[i--], str[j]);
}
int main()
{
char str[] = "Hey there, it's w3wiki" ;
moveSpaceInFront(str);
cout << str;
return 0;
}
|
Java
class GFG
{
static void moveSpaceInFront( char str[])
{
int i = str.length- 1 ;
for ( int j = i; j >= 0 ; j--)
if (str[j] != ' ' )
{
char c = str[i];
str[i] = str[j];
str[j] = c;
i--;
}
}
public static void main(String[] args)
{
char str[] = "Hey there, it's w3wiki" .toCharArray();
moveSpaceInFront(str);
System.out.println(String.valueOf(str));
}
}
|
Python3
def moveSpaceInFront(s):
i = len (s) - 1 ;
for j in range (i, - 1 , - 1 ):
if (s[j] ! = ' ' ):
s = swap(s, i, j);
i - = 1 ;
return s;
def swap(c, i, j):
c = list (c)
c[i], c[j] = c[j], c[i]
return ''.join(c)
s = "Hey there, it's w3wiki" ;
s = moveSpaceInFront(s);
print (s);
|
C#
using System;
class GFG
{
static void moveSpaceInFront( char []str)
{
int i = str.Length-1;
for ( int j = i; j >= 0; j--)
if (str[j] != ' ' )
{
char c = str[i];
str[i] = str[j];
str[j] = c;
i--;
}
}
public static void Main()
{
char []str = "Hey there, it's w3wiki" .ToCharArray();
moveSpaceInFront(str);
Console.WriteLine(String.Join( "" ,str));
}
}
|
Javascript
<script>
function moveSpaceInFront(str)
{
let i = str.length-1;
for (let j = i; j >= 0; j--)
if (str[j] != ' ' )
{
let c = str[i];
str[i] = str[j];
str[j] = c;
i--;
}
}
let str = "Hey there, it's w3wiki" .split( "" );
moveSpaceInFront(str);
document.write((str).join( "" ));
</script>
|
Output
Heythere,it'sw3wiki
Time complexity-: O(n)
Auxiliary Space-: O(1)
Method 2 (Without using swap): The idea is to copy all non-space characters to end. Finally copy spaces.
C++
#include<bits/stdc++.h>
using namespace std;
void moveSpaceInFront( char str[])
{
int i = strlen (str);
for ( int j=i; j >= 0; j--)
if (str[j] != ' ' )
str[i--] = str[j];
while (i >= 0)
str[i--] = ' ' ;
}
int main()
{
char str[] = "Hey there, it's w3wiki" ;
moveSpaceInFront(str);
cout << str;
return 0;
}
|
Java
class GFG
{
static void moveSpaceInFront( char str[])
{
int i = str.length- 1 ;
for ( int j = i; j >= 0 ; j--)
if (str[j] != ' ' )
str[i--] = str[j];
while (i >= 0 )
str[i--] = ' ' ;
}
public static void main(String[] args)
{
char str[] = "Hey there, it's w3wiki" .toCharArray();
moveSpaceInFront(str);
System.out.println(String.valueOf(str));
}
}
|
Python3
def moveSpaceInFront(s):
i = len (s) - 1 ;
for j in range (i, - 1 , - 1 ):
if (s[j] ! = ' ' ):
s = s[:i] + s[j] + s[i + 1 :]
i - = 1 ;
while (i > = 0 ):
s = s[:i] + ' ' + s[i + 1 :]
i - = 1
return s;
s = "Hey there, it's w3wiki" ;
s = moveSpaceInFront(s);
print (s);
|
C#
using System;
class GFG
{
static void moveSpaceInFront( char []str)
{
int i = str.Length-1;
for ( int j = i; j >= 0; j--)
if (str[j] != ' ' )
str[i--] = str[j];
while (i >= 0)
str[i--] = ' ' ;
}
public static void Main(String[] args)
{
char []str = "Hey there, it's w3wiki" .
ToCharArray();
moveSpaceInFront(str);
Console.WriteLine(String.Join( "" ,str));
}
}
|
Javascript
<script>
function moveSpaceInFront(str)
{
var i = str.length - 1;
for ( var j = i; j >= 0; j--)
if (str[j] !== " " )
str[i--] = str[j];
while (i >= 0) str[i--] = " " ;
}
var str = "Hey there, it's w3wiki" .split( "" );
moveSpaceInFront(str);
document.write(str.join( "" ));
</script>
|
Output
Heythere,it'sw3wiki
Time complexity-: O(n)
Auxiliary Space -:O(1)
If you like w3wiki(We know you do!) and would like to contribute, you can also write an article using write.w3wiki.net or mail your article to review-team@w3wiki.net.