Table of Contents
Problem Statement
In this problem, we are given a text string having some number of words that are placed among the spaces. Words can have only lowercase english letters. Ofcourse each words are separated with at least one space. Also The text has at least one word.
e.g. text= ” practice makes perfect”
As we can see there are arbitrary number of spaces.
We have to convert a text into such a format in which there are equal number of spaces between each word and if any space remains, then those will be accumulated after the last word.
We don’t have to change the total number of spaces. Also the sequence of words should not be changed.
Example
text = " practice makes perfect"
"practice makes perfect "
Explanation:
It has 7 spaces and 3 words.
We will equally divide the 7 spaces to fit the 3-1=2 gaps between the words. Thus, in our output we will have 7/2=3 spaces between the words and 7-6=1 remaining space will be accumulated after last word.
Therefore output would be “practice makes perfect “.
text = " this is a sentence "
"this is a sentence"
Explanation:
There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.
Approach
We have to do two tasks here. First is to get all the words from the give input string. Second, we should count the spaces. For this purpose, we are linearly traversing the input string. If the character found is a space then we do two things, one is to count this space and other is to terminate the current word and insert it into the word list.
If the current character is not space then we just append it into our current word. At last, if any word is appearing after last space, we add that word too after the traversal.
So, we get the number of spaces and the words in the input string. Now we have to divide the spaces equally among the words. But we have to notice an edge case that there may be just a single word in the input string, so we have to just return a string which has this word followed by all the spaces. Otherwise, we have to divide these spaces equally among the list of words.
Suppose if there are n words, then the positions between the words are n-1.
Thus, we have to divide the spaces (let count) into these n-1 places
hence floor(count/n-1) will be the width of spaces which will separate all the words.
and the remaining number of spaces will be appended after the last word.
i.e. count%(n-1) will be the remaining number of spaces.
Finally, we will keep on appending each word and the floor(count/n-1) number of spaces between each pair of words and count%(n-1) number of spaces after the last word and return the final string.
Implementation
C++ Program Rearrange Spaces Between Words Leetcode Solution
#include <bits/stdc++.h>
using namespace std;
string reorderSpaces(string text)
{
int count=0;
stringstream ss;
vector<string> list;
for(int i=0;i<text.length();i++){
if(text[i]==' '){
if(ss.str().size()>0)list.push_back(ss.str());//if there is some character present, only then
// insert into list
count++;
ss.str("");//empties the stringstream object
}else{
ss<<text[i];
}
}
if(ss.str().size()>0)list.push_back(ss.str());//in case if any string is after the last space, that is not inserted into list.
int wid=0,rem=0,l=0;
if(list.size()==1){
wid=0;
rem=count;
}else{
/*number of positions between n words is n-1. thus l = list.size()-1*/
l=list.size()-1;
/*distributing the spaces equally in l places*/
wid=count/l;
/*and the remaining spaces will be appended at last*/
rem=count%l;
}
ss.str("");
for(int i=0;i<list.size();i++){
ss<<list[i];//appending a word
int w=wid;
if(i<list.size()-1)
while(w--!=0)ss<<' ';//appending spaces which is width we calculated above
}
while(rem--!=0)ss<<' ';//finally appending all the remaining spaces
return ss.str();
}
int main()
{
cout << reorderSpaces(" this is a sentence ");
}this is a sentence
Java Program for Rearrange Spaces Between Words Leetcode Solution
import java.util.*;
import java.lang.*;
class Rextester
{
public static void main(String args[])
{
System.out.println(reorderSpaces(" this is a sentence "));
}
public static String reorderSpaces(String text)
{
int count=0;
StringBuilder sb=new StringBuilder();
List<String> list=new ArrayList<String>();
for(int i=0;i<text.length();i++){
if(text.charAt(i)==' '){
if(sb.length()>0)list.add(sb.toString());//if there is some non-space character also present, only then
// insert into list
count++;//counting spaces
sb=new StringBuilder();//empties the stringstream object
}else{
sb.append(text.charAt(i));
}
}
if(sb.length()>0)list.add(sb.toString());//in case if any string is after the last space, that is not inserted into list.
int wid=0,rem=0,l=0;
if(list.size()==1){
wid=0;
rem=count;
}else{
/*number of positions between n words is n-1. thus l = list.size()-1*/
l=list.size()-1;
/*distributing the spaces equally in l places*/
wid=count/l;
/*and the remaining spaces will be appended at last*/
rem=count%l;
}
sb=new StringBuilder();
for(int i=0;i<list.size();i++){
sb.append(list.get(i));//appending a word
int w=wid;
if(i<list.size()-1)
while(w--!=0)sb.append(' ');//appending spaces which is width we calculated above
}
while(rem--!=0)sb.append(' ');//finally appending all the remaining spaces
return sb.toString();
}
}this is a sentence
Complexity Analysis for Rearrange Spaces Between Words Leetcode Solution
Time Complexity
O(n): Firstly, we are traversing our input string linearly and storing the space separated words into our list. Then, we are creating our output string in linear time. Thus, time complexity will be O(n).
Space Complexity
O(n): We have used linear extra space in form of List of words and string builder (string stream in case of cpp).