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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
How many Leetcode problems Googlers have solved? #sde #google • The Code Skool • 92,673 views views
Watch 9 more video solutions →Practice Rearrange Spaces Between Words with our built-in code editor and test cases.
Practice on FleetCode