Leetcode – Rearrange Spaces Between Words Solution

Spread the love

The “Rearrange Spaces Between Words” problem on Leetcode is a classic coding problem focusing on string manipulation. The problem requires you to rearrange the spaces between words in a given string so that the spaces are distributed as evenly as possible. Additionally, the words should be shifted to the left, and if the spaces can’t be distributed evenly, the extra spaces should be placed at the end of the resulting string.

This article will provide an in-depth look at how to solve the problem, including the approach, code explanation, and potential improvements.

Problem Statement

Here’s the original problem statement from Leetcode:

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 each 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:

Input: text = "this is a sample string"
Output: "this  is  a  sample  string  "

Approach to Solving the Problem

Before diving into the coding, let’s first break down the problem into smaller sub-tasks.

  1. Count the total number of spaces in the given string.
  2. Split the string into a list of words.
  3. Determine the maximum number of spaces that can be equally distributed between the words.
  4. Arrange the words with the calculated spaces between them.
  5. If there are extra spaces, append them at the end of the resulting string.

Counting the Total Spaces

The first task is to count the number of spaces in the given string. We can easily achieve this by looping through the string and counting each space character.

Splitting the String into Words

Python’s split() function can easily split a string by a given separator. By default, it uses whitespace as the separator. So, str.split() can be used to split the given string into a list of words.

Maximum Spaces Between Words

To find the maximum number of spaces that can be equally distributed between words, we need to divide the total number of spaces by (n-1), where n is the total number of words. The integer division operator // in Python performs floor division, discarding the fractional part, which is precisely what we need.

Arranging the Words

To arrange the words, we can use Python’s join() method, which joins the elements of an iterable into a single string. We’ll need to create a string made up of the calculated maximum number of spaces and use it as the separator in join().

Extra Spaces

If any spaces are left over after equal distribution, they should be added to the end of the resulting string.

Code Implementation

Here’s the Python code to implement the approach outlined above:

def reorderSpaces(text):
    # Count the number of spaces
    space_count = text.count(" ")
    
    # Split the string into words
    words = text.split()
    
    # Calculate the number of words
    num_words = len(words)
    
    if num_words == 1:
        return words[0] + " " * space_count
    
    # Calculate maximum number of spaces between each pair of adjacent words
    max_spaces = space_count // (num_words - 1)
    
    # Calculate extra spaces to be added at the end
    extra_spaces = space_count % (num_words - 1)
    
    # Create a separator made up of max_spaces
    separator = " " * max_spaces
    
    # Join words with the separator
    result = separator.join(words)
    
    # Add extra spaces at the end
    result += " " * extra_spaces
    
    return result

Code Explanation

  • We first count the number of spaces in the text and split the text into a list of words.
  • If there’s only one word, we return that word followed by all the spaces.
  • We then calculate the maximum number of spaces that can be equally distributed between each pair of adjacent words.
  • Using the join() function, we combine the words, inserting the calculated maximum number of spaces between each pair of adjacent words.
  • Finally, any extra spaces are added to the end.

Time Complexity

The time complexity for this solution is O(n), where n is the length of the input string. Counting spaces takes O(n), splitting the string takes O(n), and joining words also takes O(n).

Space Complexity

The space complexity is O(m), where m is the number of words, due to the storage required for the list of words.

Improvements and Extensions

  1. If you know that the text will contain only spaces and lowercase letters, you can optimize space by doing in-place manipulation.
  2. If you need to deal with different types of whitespace (tabs, newlines, etc.), you would have to modify the split() and count() functions accordingly.

Conclusion

The “Rearrange Spaces Between Words” problem is an excellent exercise in string manipulation. It tests your understanding of basic string operations, like splitting, joining, and counting characters. The problem is relatively straightforward but serves as good practice for anyone looking to improve their coding skills.

Leave a Reply