Problem Description

Given a string text consisting of words and spaces, your task is to rearrange the spaces between the words so that the spaces are evenly distributed between the words. If there are extra spaces left after even distribution, they should be placed at the end of the string. The rearranged string must have the same length as the original text.

• Each word is a sequence of non-space characters.
• There will always be at least one word in text.
• There is only one valid solution for each input.
• You cannot reuse or drop any spaces or words.

Example: If text = " this is a sentence ", the output should be "this is a sentence" (with evenly distributed spaces).

Thought Process

When approaching this problem, the first instinct might be to split the string into words and then simply join them with a single space. However, the challenge is to distribute all the original spaces as evenly as possible between the words, with any leftover spaces going to the end. This means we need to:

• Count the total number of spaces in the original string.
• Determine the number of gaps between the words (which is one fewer than the number of words).
• Evenly divide the spaces among these gaps, putting any remainder at the end.

A brute-force approach might involve repeatedly adding one space at a time between words, but that's inefficient. Instead, we can use division and modulo operations to quickly determine how many spaces go between each word and how many are left for the end.

Solution Approach

Here’s a step-by-step guide to solving the problem efficiently:

1. Count Spaces:
   • Iterate through the string and count the number of space characters.
2. Split Into Words:
   • Use a string splitting function (like split() in most languages) to extract all the words, ignoring extra spaces.
3. Calculate Gaps:
   • The number of gaps between words is number_of_words - 1.
4. Distribute Spaces:
   • If there is more than one word, divide the total spaces by the number of gaps to get the minimum spaces per gap.
   • The remainder (using modulo) is the number of spaces that will go at the end.
   • If there is only one word, all spaces go to the end.
5. Rebuild the String:
   • Join the words with the calculated number of spaces between each.
   • Add the extra spaces at the end.

This approach is efficient because it only requires a few passes through the string and uses simple arithmetic to distribute the spaces.

Example Walkthrough

Let’s walk through the example text = " practice makes perfect":

• Step 1: Count spaces. There are 7 spaces.
• Step 2: Split into words. The words are ["practice", "makes", "perfect"].
• Step 3: Calculate gaps. There are 3 words, so 2 gaps.
• Step 4: Distribute spaces.
  • Spaces per gap: 7 // 2 = 3
  • Extra spaces at the end: 7 % 2 = 1
• Step 5: Build the result.
  • Join words with 3 spaces: "practice makes perfect"
  • Add 1 space at the end: "practice makes perfect "

The final result is "practice makes perfect ".

Code Implementation

class Solution:
    def reorderSpaces(self, text: str) -> str:
        spaces = text.count(' ')
        words = text.split()
        if len(words) == 1:
            # All spaces go to the end if only one word
            return words[0] + ' ' * spaces
        gaps = len(words) - 1
        spaces_per_gap = spaces // gaps
        extra_spaces = spaces % gaps
        return (' ' * spaces_per_gap).join(words) + ' ' * extra_spaces
      

class Solution {
public:
    string reorderSpaces(string text) {
        int spaces = 0;
        vector<string> words;
        string word;
        for (char c : text) {
            if (c == ' ') {
                spaces++;
                if (!word.empty()) {
                    words.push_back(word);
                    word.clear();
                }
            } else {
                word += c;
            }
        }
        if (!word.empty()) words.push_back(word);
        if (words.size() == 1) {
            return words[0] + string(spaces, ' ');
        }
        int gaps = words.size() - 1;
        int spaces_per_gap = spaces / gaps;
        int extra_spaces = spaces % gaps;
        string result;
        for (int i = 0; i < words.size(); ++i) {
            result += words[i];
            if (i != words.size() - 1)
                result += string(spaces_per_gap, ' ');
        }
        result += string(extra_spaces, ' ');
        return result;
    }
};
      

class Solution {
    public String reorderSpaces(String text) {
        int spaces = 0;
        List<String> words = new ArrayList<>();
        StringBuilder word = new StringBuilder();
        for (char c : text.toCharArray()) {
            if (c == ' ') {
                spaces++;
                if (word.length() > 0) {
                    words.add(word.toString());
                    word.setLength(0);
                }
            } else {
                word.append(c);
            }
        }
        if (word.length() > 0) words.add(word.toString());
        if (words.size() == 1) {
            return words.get(0) + " ".repeat(spaces);
        }
        int gaps = words.size() - 1;
        int spacesPerGap = spaces / gaps;
        int extraSpaces = spaces % gaps;
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < words.size(); i++) {
            result.append(words.get(i));
            if (i != words.size() - 1) {
                result.append(" ".repeat(spacesPerGap));
            }
        }
        result.append(" ".repeat(extraSpaces));
        return result.toString();
    }
}
      

var reorderSpaces = function(text) {
    let spaces = 0;
    let words = [];
    let word = '';
    for (let c of text) {
        if (c === ' ') {
            spaces++;
            if (word.length > 0) {
                words.push(word);
                word = '';
            }
        } else {
            word += c;
        }
    }
    if (word.length > 0) words.push(word);
    if (words.length === 1) {
        return words[0] + ' '.repeat(spaces);
    }
    let gaps = words.length - 1;
    let spacesPerGap = Math.floor(spaces / gaps);
    let extraSpaces = spaces % gaps;
    let result = words.join(' '.repeat(spacesPerGap));
    result += ' '.repeat(extraSpaces);
    return result;
};
      

Time and Space Complexity

Brute-force approach: If we attempted to insert spaces one at a time between words, the time complexity could be O(N²), where N is the length of the string, due to repeated string concatenation.

Optimized approach (as above):

• Time Complexity: O(N), where N is the length of text. We make a constant number of passes over the input: one to count spaces and extract words, another to build the output.
• Space Complexity: O(N), since we store the words and the result string, both of which are at most the size of the input.

These bounds are optimal for this problem, as every character must be examined at least once.

Summary

The key to solving "Rearrange Spaces Between Words" efficiently is to recognize that the problem is about counting and distributing spaces, not about complex string manipulation. By counting spaces and words, then using simple arithmetic to determine the distribution, we can construct the result in linear time. This approach is both concise and robust, ensuring all original spaces are used and the output string matches the required length and format.