Skip to main content
Talentd

Rearrange Spaces Between Words - Solution & Explanation

EasyString19 min readAsked at: Google
Practice this problem

Problem Statement

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.

This C solution reads through the input string to count the number of spaces, then splits the string into words ignoring original spaces. It calculates the number of spaces to place between words and appends the necessary spaces. Finally, it produces the result string by inserting calculated spaces between extracted words and remaining spaces at the end.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input string as reading through it is the most time-consuming operation. Space Complexity: O(n), for storing the result string which is directly proportional to the input length.

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.

In this C implementation, we avoid splitting the string and handle characters directly to distinguish between words and spaces dynamically. This method involves manually tracking when words begin and end, appropriately allocating spaces between and after words.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as it involves a single traversal of the text array. Space Complexity: O(n), due to the necessity to create a new array for the result.

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Split and Redistribute Spaces

Time Complexity: O(n), where n is the length of the input string as reading through it is the most time-consuming operation. Space Complexity: O(n), for storing the result string which is directly proportional to the input length.

Simultaneous Traversal and Reconstruction

Time Complexity: O(n), as it involves a single traversal of the text array. Space Complexity: O(n), due to the necessity to create a new array for the result.

String Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Split and Redistribute SpacesO(n)O(n)Best for readability and quick implementation using built-in string split and join operations.
Simultaneous Traversal and ReconstructionO(n)O(1) extraUseful when minimizing auxiliary memory or demonstrating manual string parsing logic.

Video Solution

1592. Rearrange Spaces Between Words (Leetcode Easy) • Programming Live with Larry • 812 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Rearrange Spaces Between Words with our built-in code editor and test cases.

Practice on FleetCode
Previous

Text Justification