1592. Rearrange Spaces Between Words
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 43.6%
Problem Breakdown
The problem requires rearranging spaces in a given string such that there are an equal number of spaces between every pair of adjacent words, with the maximum possible number of spaces used. If it’s not possible to distribute all spaces equally, the extra spaces should be placed at the end of the string. The input is a string text containing lowercase English letters and spaces. The output should be a rearranged version of the input string with spaces distributed as described.
Inputs:
- A single string
text.
Outputs:
- A string with spaces rearranged according to the rules specified.
Implicit Constraints or Tricky Edge Cases:
- The string contains at least one word.
- The number of words and spaces can be such that no spaces are between words (e.g., if there is only one word).
- The input string might start or end with spaces, or have multiple consecutive spaces between words.
Intuition
A brute-force approach would involve counting the total number of spaces and words, then manually inserting spaces between words. However, this approach can be inefficient in terms of both time and space complexity, especially if the string is long.
The key insight is to use Python’s built-in string methods to split the text into words and count the spaces efficiently. Once we have the number of words and spaces, we can calculate how many spaces should go between each word and how many extra spaces should be placed at the end. This approach leverages efficient string operations and reduces unnecessary complexity.
Approach
-
Count Spaces and Words:
- Use
text.count(' ')to count the total number of spaces. - Use
text.split()to split the text into words, which automatically handles multiple consecutive spaces.
- Use
-
Calculate Spaces Between Words and Extra Spaces:
- If there is more than one word, calculate the number of spaces between each pair of words as
total_spaces // (len(words) - 1). - Calculate the number of extra spaces as
total_spaces % (len(words) - 1).
- If there is more than one word, calculate the number of spaces between each pair of words as
-
Construct the Result String:
- Use
' '.join(words)to join the words with a single space. - Add the calculated spaces between each word and append any extra spaces at the end.
- Use
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string
text. This is because we are counting spaces and splitting the string, both of which are linear operations. - Space Complexity: O(n), as we store the list of words and the final result string, both of which can be up to the size of the input string.
Solution
def reorderSpaces(text: str) -> str:
total_spaces = text.count(' ')
words = text.split()
if len(words) == 1:
# If there's only one word, all spaces go at the end
return words[0] + ' ' * total_spaces
spaces_between_words = total_spaces // (len(words) - 1)
extra_spaces = total_spaces % (len(words) - 1)
# Join words with the calculated number of spaces and add extra spaces at the end
return (' ' * spaces_between_words).join(words) + ' ' * extra_spaces
Edge Cases Handled
- Single Word: If there is only one word, all spaces are placed at the end.
- No Spaces Between Words: If the input string has no spaces between words, they are added during the join operation.
- Trailing and Leading Spaces: The
split()method automatically handles leading and trailing spaces, ensuring that only valid words are considered.