Rearrange Spaces Between Words Leetcode Solution


Difficulty Level Easy
Frequently asked in Google
String

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:

Rearrange Spaces Between Words Leetcode Solution

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).