algoadvance

Given a string text of words separated by spaces, rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and any extra spaces are inserted at the end. This should maintain the relative order of the words.

Example

• Input: " this is a sentence "

• Output: "this is a sentence"

• Input: " practice makes perfect"
• Output: "practice makes perfect "

The number of spaces between words should be maximized and any extra spaces should be placed at the end if there are not enough pairs of adjacent words to use all spaces evenly.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the input string?
   • Can the string contain leading or trailing spaces, or only spaces between words?
2. Output Format:
   • Should the resulting string maintain the order of words as they appeared in the input string? (Assuming yes based on the example).

Strategy

1. Count Spaces: First, count the total number of spaces in the string.
2. Extract Words: Use Python string’s split() method to extract words, which will automatically handle multiple spaces.
3. Calculate Spaces: Compute the number of spaces that should go between words and how many extra spaces remain.
4. Construct Result: Build the final string combining words with appropriate spaces in between and adding any remaining spaces at the end.

Code

def reorderSpaces(text: str) -> str:
    # Step 1: Total number of spaces in the original text
    total_spaces = text.count(' ')
    
    # Step 2: Extract all words
    words = text.split()
    num_of_words = len(words)
    
    if num_of_words == 1:
        # If there is only one word, all spaces go to the end
        return words[0] + ' ' * total_spaces
    
    # Step 3: Calculate space between words and remaining spaces
    spaces_between_words = total_spaces // (num_of_words - 1)
    remaining_spaces = total_spaces % (num_of_words - 1)
    
    # Step 4: Generate the final string
    reordered_text = (' ' * spaces_between_words).join(words) + ' ' * remaining_spaces
    
    return reordered_text

# Example usage
print(reorderSpaces("  this   is  a sentence "))  # Output: "this   is   a   sentence"
print(reorderSpaces(" practice   makes   perfect"))  # Output: "practice   makes   perfect "

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. The string splitting and joining operations both traverse the entire string.
• Space Complexity: O(1) excluding the space used for the input and output strings. The additional space used is minimal and doesn’t grow with input size.

This solution is efficient and should handle the problem constraints well.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?