We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rearrange Spaces Between Words

Number: 1714

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string that contains words interleaved with spaces, rearrange the spaces so that the spaces between each pair of adjacent words are equal and maximized. Any extra spaces that cannot be evenly distributed must be placed at the end of the string.

Key Insights

  • Count the total number of spaces in the string.
  • Extract words by splitting the string on spaces.
  • If there is more than one word, compute the number of spaces between words (total spaces divided by (number of words - 1)).
  • Compute any remaining spaces that cannot be evenly distributed.
  • In the case of a single word, append all spaces after the word.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string, since the string is processed once to count spaces and split words. Space Complexity: O(n), required for storing the split words and constructing the result string.

Solution

We use a two-step approach. First, we process the string to count the number of space characters and extract the words using a split operation. Second, we compute how many spaces should be placed between words and how many should be appended at the end. The evenly distributed spaces between words are achieved via integer division, while the remainder is appended as trailing spaces if more than one word is present. In the special case of a string containing only one word, all the counted spaces are appended at the end.

Code Solutions

# Define the function rearrangeSpaces that takes in a string text.
def rearrangeSpaces(text):
    # Count the total number of spaces in the text.
    total_spaces = text.count(" ")
    # Split the text into words using the default split (which splits by any whitespace).
    words = text.split()
    
    # Check the number of words in the list.
    num_words = len(words)
    
    # If there's only one word, append all spaces to the end of the word.
    if num_words == 1:
        return words[0] + (' ' * total_spaces)
    
    # Compute the number of spaces to be placed between each adjacent pair of words.
    spaces_between = total_spaces // (num_words - 1)
    # Compute any remaining spaces that couldn't be evenly distributed.
    trailing_spaces = total_spaces % (num_words - 1)
    
    # Join the words with the equal number of spaces and append the extra trailing spaces.
    result = (' ' * spaces_between).join(words) + (' ' * trailing_spaces)
    return result

# Example test cases.
print(rearrangeSpaces("  this   is  a sentence "))  # Output: "this   is   a   sentence"
print(rearrangeSpaces(" practice   makes   perfect"))  # Output: "practice   makes   perfect "
← Back to All Questions