Rearrange Spaces Between Words - Leetcode Solution

Problem Description:

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 every 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 1: Input: text = " this is a sentence " Output: "this is a sentence" Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces. Example 2: Input: text = " practice makes perfect" Output: "practice makes perfect " Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string. Example 3: Input: text = "hello world" Output: "hello world" Explanation: There are a total of 3 spaces and 2 words. We can divide these spaces equally between the words: 3 / (2-1) = 3 spaces.

Solution:

This is one of the string problems on leetcode. We can solve this problem by following the steps mentioned below:

First, we will count the total number of spaces and words in the given string. Then, we will calculate the required number of spaces that should be placed between each adjacent word by calculating total_spaces / (total_words - 1). We will store the quotient and remainder of the calculated value in the variables 'quotient' and 'remainder', respectively. Next, we will create a string array 'words' that will store all the individual words of the given string. We will then iterate through all the words in the 'words' array and append 'quotient' number of spaces between them and add the remaining spaces at the end of the string. Finally, we will join all the words in the 'words' array with spaces to get the final string.

Pseudo code:

total_spaces = 0 total_words = 1

for i in range(len(text)): if text[i] == ' ': total_spaces += 1 elif i > 0 and text[i-1] == ' ': total_words += 1

quotient = total_spaces // (total_words - 1) remainder = total_spaces % (total_words - 1)

words = text.split()

for i in range(len(words)-1): words[i] += ' ' * quotient

if remainder > 0: words[-1] += ' ' * remainder

return ' '.join(words)

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the given string 'text'. We iterate through the string and split it into words, which take O(n) time. Then we calculate the required number of spaces and add them to the words, which takes O(n) time. Finally, we join the words to form the final string, which takes O(n) time. Hence, the overall time complexity is O(n).

Space Complexity:

The space complexity of this solution is O(n), where n is the length of the given string 'text'. We store the individual words in an array, which takes O(n) space. Then we append spaces to the words to form the final string, which also takes O(n) space. Hence, the overall space complexity is O(n).

Code:

Below is the complete code for the solution in Python:

class Solution: def reorderSpaces(self, text: str) -> str: total_spaces = 0 total_words = 1

    for i in range(len(text)):
        if text[i] == ' ':
            total_spaces += 1
        elif i > 0 and text[i-1] == ' ':
            total_words += 1
    
    quotient = total_spaces // (total_words - 1)
    remainder = total_spaces % (total_words - 1)
    
    words = text.split()
    
    for i in range(len(words)-1):
        words[i] += ' ' * quotient
        
    if remainder > 0:
        words[-1] += ' ' * remainder
        
    return ' '.join(words)

1