# Rearrange Spaces Between Words
**Difficulty:** EASY
[External](https://leetcode.com/problems/rearrange-spaces-between-words)
Canonical: https://scaleengineer.com/dsa/problems/rearrange-spaces-between-words
**Data structures:** String
---
## Problem
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.

**Constraints:**

* `1 <= text.length <= 100`
* `text` consists of lowercase English letters and `' '`.
* `text` contains at least one word.

# Approaches
## Naive Approach with String Concatenation
This approach first extracts all words and counts the total number of spaces. Then, it calculates how many spaces should go between words and how many are left over. Finally, it reconstructs the string by repeatedly concatenating words and separators in a loop using the `+` operator. This method is straightforward to understand but highly inefficient.
**Time:** O(N^2), where N is the length of the input string. While counting spaces and splitting the string is O(N), the string concatenation in a loop dominates. If there are K words, building the string takes roughly O(K * N) time, which in the worst case is O(N^2). · **Space:** O(N^2), where N is the length of the input string. The `split` operation takes O(N) space, but the primary issue is the loop for concatenation, which creates numerous intermediate string objects. The total memory consumed by these objects can be on the order of O(N^2).
**Pros:** Conceptually simple and easy to write for beginners.
**Cons:** Extremely inefficient for time and space, especially with a large number of words, due to the nature of string immutability in Java.; Can lead to `OutOfMemoryError` for large inputs, although not an issue with the given constraints.
### Explanation
The core of this method lies in its two main phases: analysis and reconstruction.

1.  **Analysis**: The input string `text` is first processed to gather necessary information. We count the total number of space characters. Simultaneously, we extract the words. A simple way to do this is by using built-in functions like `trim()` to remove leading/trailing whitespace and `split("\\s+")` to get an array of words.

2.  **Reconstruction**: After calculating the ideal number of spaces for each gap and the leftover spaces, we build the new string. This is where the inefficiency is introduced. A `for` loop iterates through the array of words, and inside the loop, the `+` operator is used to append the current word and the separator string to a result string. In Java, strings are immutable. Each time `result = result + word` is executed, a new string object is created in memory, and the contents of the old `result` and `word` are copied into it. This process is repeated for every word, leading to quadratic time complexity.

```java
class Solution {
    public String reorderSpaces(String text) {
        int spaceCount = 0;
        for (char c : text.toCharArray()) {
            if (c == ' ') {
                spaceCount++;
            }
        }

        String[] words = text.trim().split("\\s+");
        int wordCount = words.length;

        if (wordCount == 1) {
            return words[0] + " ".repeat(spaceCount);
        }

        int spacesPerGap = spaceCount / (wordCount - 1);
        int extraSpaces = spaceCount % (wordCount - 1);

        String separator = " ".repeat(spacesPerGap);
        String trailingSpaces = " ".repeat(extraSpaces);

        String result = "";
        for (int i = 0; i < wordCount; i++) {
            result += words[i];
            if (i < wordCount - 1) {
                result += separator;
            }
        }
        result += trailingSpaces;
        
        return result;
    }
}
```
### Algorithm
*   Count the total number of spaces in `text`.
*   Get an array of words by trimming `text` and splitting by one or more whitespace characters (e.g., using `text.trim().split("\\s+")`).
*   Handle the special case where there is only one word. In this case, the result is the word followed by all the spaces.
*   Calculate the number of spaces to put in each gap: `spacesPerGap = totalSpaces / (wordCount - 1)`.
*   Calculate the number of extra spaces to put at the end: `extraSpaces = totalSpaces % (wordCount - 1)`.
*   Create a separator string consisting of `spacesPerGap` spaces.
*   Initialize an empty string, then loop through the words, appending each word and the separator using the `+` operator for string concatenation.
*   After the loop, append the extra spaces to the end.
*   Return the final string.

## Efficient Two-Pass Approach with StringBuilder
This approach significantly improves upon the naive method by using a `StringBuilder` for string construction. The initial steps of counting spaces and extracting words remain the same. However, instead of using the `+` operator in a loop, it appends words and spaces to a mutable `StringBuilder` object. This avoids the creation of countless intermediate string objects, making the string construction process linear in time.
**Time:** O(N). Counting spaces, splitting the string, and building the new string with `StringBuilder` or `String.join` are all linear time operations with respect to the input string length N. · **Space:** O(N). Space is required to store the list of words (O(N) in the worst case) and for the `StringBuilder`'s internal buffer (which will be of size N for the final string).
**Pros:** Efficient with O(N) time and space complexity.; Readable and concise, especially when using `String.join()`.; It's the standard idiomatic way to solve such problems in Java.
**Cons:** Relies on built-in functions like `trim` and `split`, which may have slightly more overhead than a purely manual implementation.
### Explanation
This method is a standard and efficient way to solve string manipulation problems in Java. It correctly identifies the performance bottleneck of the naive approach—string concatenation—and replaces it with a proper tool.

1.  **Analysis**: This phase is identical to the naive approach. We get the `spaceCount` and a list of `words`.

2.  **Reconstruction with StringBuilder**: A `StringBuilder` is initialized. We loop through our list of words. In each iteration, we append the word and, if it's not the last one, the calculated number of separator spaces. Because `StringBuilder` uses a mutable internal character array, these append operations are very fast (amortized constant time, relative to the size of the appended content). After the loop finishes, we append any extra spaces. Finally, `sb.toString()` is called once to create the final, immutable `String` object.

An even more concise implementation can use `String.join()`, which is highly optimized and uses a `StringBuilder` or a similar efficient mechanism internally.

```java
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public String reorderSpaces(String text) {
        int spaceCount = (int) text.chars().filter(c -> c == ' ').count();

        List<String> words = Arrays.stream(text.trim().split("\\s+"))
                                   .filter(s -> !s.isEmpty())
                                   .collect(Collectors.toList());
        int wordCount = words.size();

        if (wordCount == 1) {
            return words.get(0) + " ".repeat(spaceCount);
        }

        int spacesPerGap = spaceCount / (wordCount - 1);
        int extraSpaces = spaceCount % (wordCount - 1);

        String separator = " ".repeat(spacesPerGap);
        String trailingSpaces = " ".repeat(extraSpaces);

        return String.join(separator, words) + trailingSpaces;
    }
}
```
### Algorithm
*   Count the total number of spaces by iterating through the string.
*   Extract the words, for instance, by using `text.trim().split("\\s+")`.
*   Handle the single-word edge case separately.
*   Calculate `spacesPerGap` and `extraSpaces` as in the previous approach.
*   Initialize a `StringBuilder`.
*   Iterate through the list of words, appending each word to the `StringBuilder`. If it's not the last word, append `spacesPerGap` spaces.
*   After the loop, append the `extraSpaces` to the `StringBuilder`.
*   Convert the `StringBuilder` to a string and return it.

## Optimized Manual Parsing Approach
This approach is the most optimized in terms of raw performance, although it shares the same asymptotic complexity as the previous one. It avoids the overhead associated with regular expressions in `split()` and intermediate string creation from `trim()` by performing a manual, character-by-character parse of the string. It consists of two passes: a manual parsing pass to collect words and count spaces, and a construction pass using a `StringBuilder`.
**Time:** O(N). The manual parse is a single linear scan, and the string construction is also linear. The overall complexity remains O(N). · **Space:** O(N). Space is required for the `words` list and the `StringBuilder` used for construction, both of which are proportional to the input size N.
**Pros:** Potentially the fastest O(N) solution in practice due to lower constant factors.; Avoids overhead from regex and intermediate string objects during the parsing phase.
**Cons:** More verbose and complex to implement correctly compared to using high-level built-in functions.; Prone to off-by-one errors in pointer manipulation.
### Explanation
This method provides the most control over the process by handling parsing at a low level.

1.  **Manual Parsing Pass**: We iterate through the string with a single pointer `i`. We check if the current character is a space or a letter. If it's a space, we simply count it and move on. If it's a letter, we know we've found a word. We then use another pointer, `j`, to scan forward from `i` until we hit a space or the end of the string. The substring from `i` to `j` is our word, which we add to a list. We then update our main pointer `i` to `j` to avoid re-scanning the word. This loop continues until the entire string is processed.

2.  **Construction Pass**: This part is identical to the previous efficient approach. With the list of words and the total space count, we can calculate the distribution and use `StringBuilder` or `String.join` to assemble the final string efficiently.

This manual approach can be slightly faster in practice because it avoids the overhead of regex compilation/matching and the creation of a temporary trimmed string.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String reorderSpaces(String text) {
        List<String> words = new ArrayList<>();
        int spaceCount = 0;
        int n = text.length();
        int i = 0;
        while (i < n) {
            if (text.charAt(i) == ' ') {
                spaceCount++;
                i++;
            } else {
                int j = i;
                while (j < n && text.charAt(j) != ' ') {
                    j++;
                }
                words.add(text.substring(i, j));
                i = j;
            }
        }

        int wordCount = words.size();
        if (wordCount == 1) {
            return words.get(0) + " ".repeat(spaceCount);
        }

        int spacesPerGap = spaceCount / (wordCount - 1);
        int extraSpaces = spaceCount % (wordCount - 1);

        StringBuilder sb = new StringBuilder();
        sb.append(String.join(" ".repeat(spacesPerGap), words));
        sb.append(" ".repeat(extraSpaces));
        
        return sb.toString();
    }
}
```
### Algorithm
*   Initialize an empty `List<String>` for words and an integer `spaceCount` to 0.
*   Iterate through the input string `text` with an index `i`.
*   If the character at `i` is a space, increment `spaceCount` and advance `i`.
*   If the character is a letter, it marks the start of a word. Use a second pointer `j` to find the end of the word (the next space or end of string).
*   Extract the word using `text.substring(i, j)` and add it to the list.
*   Update `i` to `j` to continue scanning from where the word ended.
*   After this first pass, you have the list of words and the total space count.
*   The second pass is for construction: calculate space distribution and use a `StringBuilder` (or `String.join`) to build the final string, same as in the previous approach.

# Solutions
### Java

```java
class Solution {
public
  String reorderSpaces(String text) {
    int cnt = 0;
    for (char c : text.toCharArray()) {
      if (c == ' ') {
        ++cnt;
      }
    }
    String[] words = text.split("\\s+");
    List<String> res = new ArrayList<>();
    for (String w : words) {
      if (!"".equals(w)) {
        res.add(w);
      }
    }
    int m = res.size() - 1;
    if (m == 0) {
      return res.get(0) + " ".repeat(cnt);
    }
    String ans = String.join(" ".repeat(cnt / m), res);
    ans += " ".repeat(cnt % m);
    return ans;
  }
}

```

### Python

```python
class Solution:
    def reorderSpaces(self, text: str) -> str: cnt = text . count(' ') words = text . split() m = len(words) - 1 if m == 0: return words[0] + ' ' * cnt return (' ' * (cnt // m)). join(words) + ' ' * (cnt % m)

```

### CPP

```cpp
class Solution {
public:
  string reorderSpaces(string text) {
    int spaces = ranges ::count(text, ' ');
    auto words = split(text);
    if (words.size() == 1) {
      return words[0] + string(spaces, ' ');
    }
    int cnt = spaces / (words.size() - 1);
    int mod = spaces % (words.size() - 1);
    string result = join(words, string(cnt, ' '));
    result += string(mod, ' ');
    return result;
  }

private:
  vector<string> split(const string &text) {
    vector<string> words;
    istringstream stream(text);
    string word;
    while (stream >> word) {
      words.push_back(word);
    }
    return words;
  }
  string join(const vector<string> &words, const string &separator) {
    ostringstream result;
    for (size_t i = 0; i < words.size(); ++i) {
      result << words[i];
      if (i < words.size() - 1) {
        result << separator;
      }
    }
    return result.str();
  }
};

```