LeetCode 1592 - Rearrange Spaces Between Words

LeetCode Problem 1592

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem requires rearranging spaces in a given string text so that all words are separated by the maximum possible equal number of spaces, and any leftover spaces are placed at the end of the string. The input text consists of lowercase English letters and spaces, and it is guaranteed to contain at least one word, which simplifies handling empty inputs.

The output is a string of the same length as the input, where the spacing between words is uniform wherever possible. The constraints 1 <= text.length <= 100 indicate that the input size is small, so even a straightforward solution with linear passes over the string is efficient.

Key edge cases to consider include strings with only one word, strings where spaces cannot be evenly distributed among words, and strings with leading, trailing, or multiple consecutive spaces.

Approaches

Brute Force

A brute-force approach would involve iterating through the string, counting spaces and words manually, then repeatedly inserting spaces between words until all spaces are exhausted. While correct, this method is cumbersome because it involves manual space management and multiple passes over the string. Although acceptable for the given constraints, it is unnecessarily complex.

Optimal Approach

The optimal approach relies on a few observations. First, we can count the total spaces by iterating once over the string. Next, we extract all words by splitting the string on whitespace. If there is more than one word, the number of spaces between words is the integer division of total spaces by (number of words - 1). Any remainder from this division becomes the extra spaces appended at the end. If there is only one word, all spaces are appended after it.

This approach is simple, requires only linear scans of the input, and directly constructs the output in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Multiple passes for inserting spaces, manually managing string concatenation
Optimal	O(n)	O(n)	Count spaces and words once, calculate spacing, construct final string

Algorithm Walkthrough

1. Count the total number of spaces in text. This can be done with a single iteration or using a built-in count method.
2. Split text into a list of words using whitespace as the delimiter. This will automatically remove extra spaces.
3. Determine the number of words. If there is only one word, all spaces will go at the end.
4. Calculate the number of spaces to place between words. This is total_spaces // (number_of_words - 1). If there is only one word, this value is zero.
5. Calculate any leftover spaces using the modulo operation total_spaces % (number_of_words - 1). These extra spaces are appended to the end.
6. Construct the final string by joining words with the calculated number of spaces and then appending any extra spaces at the end.

Why it works: The algorithm works because it explicitly counts the resources (spaces) and evenly distributes them according to the number of gaps between words. The modulo operation ensures no space is lost, and the join operation guarantees proper spacing.

Python Solution

class Solution:
    def reorderSpaces(self, text: str) -> str:
        total_spaces = text.count(' ')
        words = text.split()
        if len(words) == 1:
            return words[0] + ' ' * total_spaces
        
        spaces_between_words = total_spaces // (len(words) - 1)
        extra_spaces = total_spaces % (len(words) - 1)
        
        return (' ' * spaces_between_words).join(words) + ' ' * extra_spaces

The implementation counts the spaces, splits the text into words, handles the single-word special case, calculates spacing, and finally constructs the output string efficiently. The ' '.join(words) operation ensures words are concatenated with the exact number of spaces.

Go Solution

import (
    "strings"
)

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

The Go version uses strings.Count to count spaces and strings.Fields to split words. strings.Repeat handles repeated spaces. The logic is identical to Python, with attention to slice handling and string concatenation in Go.

Worked Examples

Example 1: text = " this is a sentence "

Step	Words	Total Spaces	Spaces Between	Extra Spaces	Result
Initial	["this","is","a","sentence"]	9	3	0	"this is a sentence"

Example 2: text = " practice makes perfect"

Step	Words	Total Spaces	Spaces Between	Extra Spaces	Result
Initial	["practice","makes","perfect"]	7	3	1	"practice makes perfect "

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Counting spaces, splitting words, and constructing output each require a single pass over the string.
Space	O(n)	Storing words and constructing the output string require linear space relative to input size.

The approach is efficient because it avoids nested loops or repeated string concatenations, working directly with counts and splits.

Test Cases

# Provided examples
assert Solution().reorderSpaces("  this   is  a sentence ") == "this   is   a   sentence"
assert Solution().reorderSpaces(" practice   makes   perfect") == "practice   makes   perfect "

# Single word with spaces
assert Solution().reorderSpaces(" word ") == "word "

# Multiple spaces but uneven distribution
assert Solution().reorderSpaces(" a  b c ") == "a b c  "

# No extra spaces needed
assert Solution().reorderSpaces("hello world") == "hello world"

# All spaces at the beginning
assert Solution().reorderSpaces("    one two") == "one   two "

Test	Why
" this is a sentence "	Validates multiple spaces between words with no leftover
" practice makes perfect"	Validates leftover space placement at the end
" word "	Tests single-word handling
" a b c "	Tests uneven space distribution
"hello world"	No redistribution needed
" one two"	Leading spaces handled correctly

Edge Cases

Single-word input: A string with only one word should have all spaces appended at the end. This prevents division by zero when calculating spaces between words.

All spaces at one end: Leading or trailing spaces must not affect word extraction; splitting by whitespace automatically handles this.

Uneven space distribution: When spaces cannot be evenly distributed, the modulo ensures leftover spaces are added at the end, maintaining string length integrity and uniformity between word gaps.