How do you solve Rearrange Spaces Between Words on LeetCode?

Rearrange Spaces Between Words (LeetCode #1592) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Count total spaces and words efficiently.

What is the brute force solution for Rearrange Spaces Between Words?

The brute force approach for Rearrange Spaces Between Words is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves counting the spaces and words, then manually reconstructing the string by inserting spaces between words. This method is straightforward but inefficient as it may involve multiple iterations over the string. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Rearrange Spaces Between Words?

Rearrange Spaces Between Words uses the following concepts: String. The recommended patterns to study are: String Manipulation, Greedy Algorithms.

What are the interview tips for Rearrange Spaces Between Words?

Always clarify edge cases with the interviewer. Think aloud while coding to show your thought process. Test your solution with different inputs to ensure correctness.

What are common mistakes when solving Rearrange Spaces Between Words?

Not accounting for the case with only one word. Forgetting to handle extra spaces correctly.

#1592

Rearrange Spaces Between Words

Easy

StringString ManipulationGreedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach efficiently counts spaces and words, calculates how to distribute spaces, and constructs the result in a single pass. This method minimizes unnecessary iterations and string manipulations.

⚙️

Algorithm

3 steps

1Step 1: Count the total number of spaces and split the text into words.
2Step 2: Calculate the number of spaces to place between each word and the extra spaces to be added at the end.
3Step 3: Use the calculated values to construct the final string in one go.

solution.py9 lines

1# Full working Python code
2
3def rearrange_spaces(text):
4    words = text.split()
5    total_spaces = text.count(' ')
6    num_words = len(words)
7    spaces_between = total_spaces // (num_words - 1) if num_words > 1 else 0
8    extra_spaces = total_spaces % (num_words - 1) if num_words > 1 else total_spaces
9    return (' ' * spaces_between).join(words) + ' ' * extra_spaces

ℹ

Complexity note: The complexity is O(n) because we only traverse the string a couple of times (once to count spaces and once to join words) without any nested iterations.

1Count total spaces and words efficiently.
2Understand how to distribute spaces evenly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.