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 <= 100text consists of lowercase English letters and ' '.text contains at least one word.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.
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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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 | — |
| 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. |
1592. Rearrange Spaces Between Words (Leetcode Easy) • Programming Live with Larry • 796 views views
Watch 9 more video solutions →Practice Rearrange Spaces Between Words with our built-in code editor and test cases.
Practice on FleetCode