1592. Rearrange Spaces Between Words - Solution

Q: Is Rearrange Spaces Between Words easy or hard?

LeetCode classifies the problem as Easy. The challenge mainly involves careful counting of spaces and handling the edge case where the sentence contains only one word.

Q: Rearrange Spaces Between Words Python/Java solution

Python solutions typically use split to extract words and string multiplication to generate spaces. Java implementations often use StringBuilder to construct the result efficiently while iterating through the words.

Q: How to solve Rearrange Spaces Between Words in O(n)?

Traverse the string once to count total spaces and identify words. Compute spaces per gap as totalSpaces divided by (wordCount - 1), and keep the remainder for the end. Rebuild the output string by joining words with the computed gap and appending leftover spaces.

Q: What is the best approach for Rearrange Spaces Between Words?

The split and redistribute approach is the most practical solution. Count the total spaces, extract all words, compute the number of spaces between words using division, and place leftover spaces at the end. This runs in O(n) time and is easy to implement in most languages.

Q: Is Rearrange Spaces Between Words asked at Google/Amazon/Meta?

This problem represents a common string manipulation pattern used in interviews at companies like Amazon and Google. Variations involving whitespace normalization or text formatting appear frequently in coding rounds.

Q: What data structure is used in Rearrange Spaces Between Words?

Most implementations rely on basic string processing and arrays or lists to store extracted words. The algorithm mainly uses counters and sequential traversal rather than complex data structures.

Q: What is the time complexity of Rearrange Spaces Between Words?

The optimal solutions run in O(n) time where n is the length of the input string. The algorithm scans the string to count spaces and words, then constructs the result string in another pass.

The problem

You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.

Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.

Return the string after rearranging the spaces.

Example 1:

Input: text = "  this   is  a sentence "
Output: "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.

Example 2:

Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

Constraints:

1 <= text.length <= 100
text consists of lowercase English letters and ' '.
text contains at least one word.

Approach overview

Problem Overview: You receive a string containing words and spaces. The goal is to redistribute all spaces so that the gaps between words are equal, while any leftover spaces appear at the end of the string. The total length must remain unchanged.

Approach 1: Split and Redistribute Spaces (O(n) time, O(n) space)

This approach separates the words first, then redistributes the spaces mathematically. Count the total number of spaces in the string by iterating once. Extract the words using a split-like operation (ignoring empty tokens). If there are k words, the number of spaces between each pair becomes totalSpaces / (k - 1) and the remainder goes to the end. Construct the final string by joining words with the calculated gap and appending leftover spaces. The algorithm performs a single pass to count spaces and another to rebuild the string, giving O(n) time complexity with O(n) extra space for storing words. This is the most straightforward approach when working with string manipulation problems.

Approach 2: Simultaneous Traversal and Reconstruction (O(n) time, O(1) extra space)

This method avoids storing all words separately. Instead, traverse the string character by character to count spaces and detect word boundaries. After determining the total space count and number of words, compute the spacing between words exactly as in the previous approach. Then perform a second traversal where you append characters of each word directly to a result buffer and insert the computed number of spaces whenever a word ends. Remaining spaces are appended after processing the last word. Because you process characters sequentially and do not store a full word list, the auxiliary memory is reduced to constant space beyond the output buffer. This technique highlights careful string traversal and reconstruction patterns often seen in interview-style parsing tasks.

Recommended for interviews: The split-and-redistribute approach is what most interviewers expect. It clearly shows that you identified the two key quantities: total spaces and number of words. Implementing the traversal version demonstrates deeper control over string parsing and memory usage. In an interview, start with the simple split solution to communicate the logic quickly, then discuss the traversal variant if optimization or in-place processing becomes a follow-up.

Approach 1: Split and Redistribute Spaces

This approach involves first counting the total number of spaces in the input text and the number of words present. We use these counts to calculate how to redistribute spaces equally between words. This involves computing the number of spaces to place between each word and the number of remaining extra spaces that should appear at the end of the string. The solution involves joining the words with calculated spaces in between them, followed by any extra spaces at the end.

Python

def rearrangeSpaces(text: str) -> str:
    total_spaces = text.count(' ')
    words = text.split()
    words_count = len(words)

    if words_count == 1:
        return words[0] + ' ' * total_spaces

    spaces_between = total_spaces // (words_count - 1)
    extra_spaces = total_spaces % (words_count - 1)

    return (' ' * spaces_between).join(words) + ' ' * extra_spaces

# Example usage
text = "  this   is  a sentence "
print(rearrangeSpaces(text))

Java

import java.util.*;

public class Solution {
    public static String rearrangeSpaces(String text) {
        int totalSpaces = 0;
        List<String> words = new ArrayList<>();
        StringBuilder wordBuilder = new StringBuilder();

        // Count spaces and collect words
        for (char c : text.toCharArray()) {
            if (c == ' ') {
                totalSpaces++;
                if (wordBuilder.length() > 0) {
                    words.add(wordBuilder.toString());
                    wordBuilder.setLength(0);
                }
            } else {
                wordBuilder.append(c);
            }
        }

        // Add last word if exists
        if (wordBuilder.length() > 0) {
            words.add(wordBuilder.toString());
        }

        int wordCount = words.size();
        int spacesBetween = wordCount > 1 ? totalSpaces / (wordCount - 1) : 0;
        int extraSpaces = wordCount > 1 ? totalSpaces % (wordCount - 1) : totalSpaces;

        StringJoiner joiner = new StringJoiner(" ".repeat(spacesBetween));
        for (String w : words) {
            joiner.add(w);
        }

        return joiner.toString() + " ".repeat(extraSpaces);
    }

    public static void main(String[] args) {
        String text = "  this   is  a sentence ";
        System.out.println(rearrangeSpaces(text));
    }
}

C++

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

string rearrangeSpaces(string text) {
    int spaceCount = 0, wordCount = 0;
    vector<string> words;
    istringstream stream(text);
    string word;

    // Count spaces and tokenize words
    for (char c : text) if (c == ' ') spaceCount++;

    while (stream >> word) {
        words.push_back(word);
        wordCount++;
    }

    int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
    int extraSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;

    string result;
    for (int i = 0; i < words.size(); i++) {
        result += words[i];
        if (i < words.size() - 1) result += string(spacesBetween, ' ');
    }
    result += string(extraSpaces, ' ');

    return result;
}

JavaScript

function rearrangeSpaces(text) {
    const totalSpaces = text.split('').filter(c => c === ' ').length;
    const words = text.trim().split(/\s+/);
    const wordCount = words.length;
    const spacesBetween = wordCount > 1 ? Math.floor(totalSpaces / (wordCount - 1)) : 0;
    const extraSpaces = wordCount > 1 ? totalSpaces % (wordCount - 1) : totalSpaces;

    return words.join(' '.repeat(spacesBetween)) + ' '.repeat(extraSpaces);
}

// Example usage
console.log(rearrangeSpaces("  this   is  a sentence "));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* rearrangeSpaces(char* text) {
    int spaceCount = 0, wordCount = 0;
    int length = strlen(text);
    char *words[100];
    char *word;
    // Count total spaces
    for (int i = 0; i < length; i++) {
        if (text[i] == ' ') spaceCount++;
    }

    // Tokenize the text by space to get words
    word = strtok(text, " ");
    while (word) {
        words[wordCount++] = word;
        word = strtok(NULL, " ");
    }

    int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
    int extraSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;
    
    // Allocate memory for the result
    char *result = (char*)malloc((length + 1) * sizeof(char));
    int pos = 0;

    // Combine words with spaces in between
    for (int i = 0; i < wordCount; i++) {
        int l = strlen(words[i]);
        strncpy(result + pos, words[i], l);
        pos += l;
        if (i < wordCount - 1) {
            memset(result + pos, ' ', spacesBetween);
            pos += spacesBetween;
        }
    }
    
    // Add extra spaces at the end
    memset(result + pos, ' ', extraSpaces);
    pos += extraSpaces;
    result[pos] = '\0';

    return result;
}

using System;
using System.Text;

public class Solution {
    public static string RearrangeSpaces(string text) {
        int spaceCount = 0;
        string[] words = text.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        foreach (char c in text) {
            if (c == ' ') spaceCount++;
        }

        int wordCount = words.Length;
        int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
        int extraSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < wordCount; i++) {
            result.Append(words[i]);
            if (i < wordCount - 1) {
                result.Append(' ', spacesBetween);
            }
        }

        result.Append(' ', extraSpaces);
        return result.ToString();
    }

    public static void Main() {
        string text = "  this   is  a sentence ";
        Console.WriteLine(RearrangeSpaces(text));
    }
}

In this concise Python solution, spaces are counted using the built-in string method count(), and words are extracted using split() which implicitly handles multiple spaces. Calculated spaces are added between words and any remaining are appended at the end.

Complexity

Time Complexity: O(n), where n is the number of characters in the input string. Space Complexity: O(n), to handle the space and word management processes.

Try this approach in the editor

Approach 2: Simultaneous Traversal and Reconstruction

This approach involves traversing the text and simultaneously reconstructing the result by keeping track of spaces and words. It avoids splitting but rather directly handles spaces and words as they appear. This method emphasizes careful management of indexes and allocation of spaces dynamically.

Python

def rearrangeSpaces(text: str) -> str:
    total_spaces = text.count(' ')
    words = text.split()
    num_words = len(words)

    if num_words == 1:
        return words[0] + ' ' * total_spaces

    spaces_between = total_spaces // (num_words - 1)
    extra_spaces = total_spaces % (num_words - 1)

    between_space = ' ' * spaces_between
    result = between_space.join(words) + (' ' * extra_spaces)

    return result

text = "  this   is  a sentence "
print(rearrangeSpaces(text))

Java

import java.util.*;

public class Solution {
    public static String rearrangeSpaces(String text) {
        int length = text.length(), spaceCount = 0;
        List<String> words = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            if (text.charAt(i) == ' ') spaceCount++;
        }

        StringTokenizer tokenizer = new StringTokenizer(text);
        while (tokenizer.hasMoreTokens()) {
            words.add(tokenizer.nextToken());
        }

        int wordCount = words.size();
        int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
        int extraSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;

        StringJoiner joiner = new StringJoiner(" ".repeat(spacesBetween));
        for (String word : words) {
            joiner.add(word);
        }

        return joiner.toString() + " ".repeat(extraSpaces);
    }

    public static void main(String[] args) {
        String text = "  this   is  a sentence ";
        System.out.println(rearrangeSpaces(text));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

string rearrangeSpaces(string text) {
    int spaceCount = 0;
    vector<string> words;
    int n = text.size();

    for (int i = 0; i < n; ++i) {
        if (text[i] == ' ') spaceCount++;
    }

    size_t start = 0, end;
    while ((end = text.find_first_not_of(' ', start)) != string::npos) {
        start = text.find_first_of(' ', end + 1);
        words.push_back(text.substr(end, start - end));
    }

    int spacesBetween = words.size() > 1 ? spaceCount / (words.size() - 1) : 0;
    int extraSpaces = words.size() > 1 ? spaceCount % (words.size() - 1) : spaceCount;

    string result;
    for (size_t i = 0; i < words.size(); ++i) {
        result += words[i];
        if (i < words.size() - 1) {
            result.append(spacesBetween, ' ');
        }
    }
    result.append(extraSpaces, ' ');

    return result;
}

int main() {
    string text = "  this   is  a sentence ";
    cout << rearrangeSpaces(text) << endl;
    return 0;
}

JavaScript

function rearrangeSpaces(text) {
    const words = text.trim().split(/\s+/);
    const totalSpaces = text.length - [...text].filter(c => c !== ' ').length;
    const wordCount = words.length;

    const spacesBetween = wordCount > 1 ? Math.floor(totalSpaces / (wordCount - 1)) : 0;
    const extraSpaces = wordCount > 1 ? totalSpaces % (wordCount - 1) : totalSpaces;

    return words.join(' '.repeat(spacesBetween)) + ' '.repeat(extraSpaces);
}

// Example usage
console.log(rearrangeSpaces("  this   is  a sentence "));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* rearrangeSpaces(char* text) {
    int spaceCount = 0, length = strlen(text);
    for (int i = 0; i < length; i++) {
        if (text[i] == ' ') spaceCount++;
    }

    char *wordStart = NULL;
    int wordCount = 0;
    for (int i = 0; i <= length; i++) {
        if ((text[i] == ' ' || text[i] == '\0') && wordStart) {
            wordCount++;
            wordStart = NULL;
        }
        else if (text[i] != ' ' && !wordStart) {
            wordStart = &text[i];
        }
    }

    int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
    int extraSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;
    
    char *result = (char*)malloc((length + 1) * sizeof(char));
    int resIndex = 0;
    wordStart = NULL;

    for (int i = 0; i <= length; i++) {
        if ((text[i] == ' ' || text[i] == '\0') && wordStart) {
            while (wordStart < &text[i]) {
                result[resIndex++] = *wordStart++;
            }
            if (wordCount-- > 1) {
                for (int s = 0; s < spacesBetween; s++) {
                    result[resIndex++] = ' ';
                }
            }
            wordStart = NULL;
        } else if (text[i] != ' ' && !wordStart) {
            wordStart = &text[i];
        }
    }

    while (extraSpaces-- > 0) {
        result[resIndex++] = ' ';
    }
    result[resIndex] = '\0';

    return result;
}

using System;
using System.Text;

public class Solution {
    public static string RearrangeSpaces(string text) {
        int spaceCount = 0;
        string[] words = text.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
        foreach (char c in text) {
            if (c == ' ') spaceCount++;
        }

        int wordCount = words.Length;
        int spacesBetween = wordCount > 1 ? spaceCount / (wordCount - 1) : 0;
        int extraSpaces = wordCount > 1 ? spaceCount % (wordCount - 1) : spaceCount;

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < wordCount; i++) {
            result.Append(words[i]);
            if (i < wordCount - 1) {
                result.Append(' ', spacesBetween);
            }
        }

        result.Append(' ', extraSpaces);
        return result.ToString();
    }

    public static void Main() {
        string text = "  this   is  a sentence ";
        Console.WriteLine(RearrangeSpaces(text));
    }
}

Python again leverages utilities like split and join, but handles spaces in a more direct approach by focusing on direct string operations to form the result, controlling white space management logically.

Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n), paralleling the input management to output storage.

Try this approach in the editor

Approach 3: String Simulation

First, we count the number of spaces in the string text, denoted as spaces. Then, we split text by spaces into an array of strings words. Next, we calculate the number of spaces that need to be inserted between adjacent words and perform the concatenation. Finally, we append the remaining spaces to the end.

The time complexity is O(n), and the space complexity is O(n), where n represents the length of the string text.

TypeScript

function reorderSpaces(text: string): string {
    const spaces = (text.match(/ /g) || []).length;
    const words = text.split(/\s+/).filter(Boolean);
    if (words.length === 1) {
        return words[0] + ' '.repeat(spaces);
    }
    const cnt = Math.floor(spaces / (words.length - 1));
    const mod = spaces % (words.length - 1);
    const result = words.join(' '.repeat(cnt));
    return result + ' '.repeat(mod);
}

func reorderSpaces(text string) string {
	cnt := strings.Count(text, " ")
	words := strings.Fields(text)
	m := len(words) - 1
	if m == 0 {
		return words[0] + strings.Repeat(" ", cnt)
	}
	return strings.Join(words, strings.Repeat(" ", cnt/m)) + strings.Repeat(" ", cnt%m)
}

Rust

impl Solution {
    pub fn reorder_spaces(text: String) -> String {
        let spaces = text.chars().filter(|&c| c == ' ').count();
        let words: Vec<&str> = text.split_whitespace().collect();
        if words.len() == 1 {
            return format!("{}{}", words[0], " ".repeat(spaces));
        }
        let cnt = spaces / (words.len() - 1);
        let mod_spaces = spaces % (words.len() - 1);
        let result = words.join(&" ".repeat(cnt));
        result + &" ".repeat(mod_spaces)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Split and Redistribute Spaces	Time Complexity: O(n), where n is the number of characters in the input string. Space Complexity: O(n), to handle the space and word management processes.
Simultaneous Traversal and Reconstruction	Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n), paralleling the input management to output storage.
String Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Split and Redistribute Spaces	O(n)	O(n)	Best for readability and quick implementation using built-in string split and join operations.
Simultaneous Traversal and Reconstruction	O(n)	O(1) extra	Useful when minimizing auxiliary memory or demonstrating manual string parsing logic.

Frequently asked questions

Is Rearrange Spaces Between Words easy or hard?

LeetCode classifies the problem as Easy. The challenge mainly involves careful counting of spaces and handling the edge case where the sentence contains only one word.

Rearrange Spaces Between Words Python/Java solution

Python solutions typically use split to extract words and string multiplication to generate spaces. Java implementations often use StringBuilder to construct the result efficiently while iterating through the words.

How to solve Rearrange Spaces Between Words in O(n)?

Traverse the string once to count total spaces and identify words. Compute spaces per gap as totalSpaces divided by (wordCount - 1), and keep the remainder for the end. Rebuild the output string by joining words with the computed gap and appending leftover spaces.

What is the best approach for Rearrange Spaces Between Words?

The split and redistribute approach is the most practical solution. Count the total spaces, extract all words, compute the number of spaces between words using division, and place leftover spaces at the end. This runs in O(n) time and is easy to implement in most languages.

Is Rearrange Spaces Between Words asked at Google/Amazon/Meta?

This problem represents a common string manipulation pattern used in interviews at companies like Amazon and Google. Variations involving whitespace normalization or text formatting appear frequently in coding rounds.

What data structure is used in Rearrange Spaces Between Words?

Most implementations rely on basic string processing and arrays or lists to store extracted words. The algorithm mainly uses counters and sequential traversal rather than complex data structures.

What is the time complexity of Rearrange Spaces Between Words?

The optimal solutions run in O(n) time where n is the length of the input string. The algorithm scans the string to count spaces and words, then constructs the result string in another pass.

Rearrange Spaces Between Words solution and explanation

The problem

Approach overview

Approach 1: Split and Redistribute Spaces

Approach 2: Simultaneous Traversal and Reconstruction

Approach 3: String Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rearrange Spaces Between Words solution and explanation

The problem

Approach overview

Approach 1: Split and Redistribute Spaces

Approach 2: Simultaneous Traversal and Reconstruction

Approach 3: String Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems