Rearrange Spaces Between Words

Easy

#1464Time: 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).

Data structures

String

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The core of this method lies in its two main phases: analysis and reconstruction.

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.
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.

1class Solution {2    public String reorderSpaces(String text) {3        int spaceCount = 0;4        for (char c : text.toCharArray()) {5            if (c == ' ') {6                spaceCount++;7            }8        }9 10        String[] words = text.trim().split("\\s+");11        int wordCount = words.length;12 13        if (wordCount == 1) {14            return words[0] + " ".repeat(spaceCount);15        }16 17        int spacesPerGap = spaceCount / (wordCount - 1);18        int extraSpaces = spaceCount % (wordCount - 1);19 20        String separator = " ".repeat(spacesPerGap);21        String trailingSpaces = " ".repeat(extraSpaces);22 23        String result = "";24        for (int i = 0; i < wordCount; i++) {25            result += words[i];26            if (i < wordCount - 1) {27                result += separator;28            }29        }30        result += trailingSpaces;31        32        return result;33    }34}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

Analysis: This phase is identical to the naive approach. We get the spaceCount and a list of words.
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.

1import java.util.Arrays;2import java.util.List;3import java.util.stream.Collectors;4 5class Solution {6    public String reorderSpaces(String text) {7        int spaceCount = (int) text.chars().filter(c -> c == ' ').count();8 9        List<String> words = Arrays.stream(text.trim().split("\\s+"))10                                   .filter(s -> !s.isEmpty())11                                   .collect(Collectors.toList());12        int wordCount = words.size();13 14        if (wordCount == 1) {15            return words.get(0) + " ".repeat(spaceCount);16        }17 18        int spacesPerGap = spaceCount / (wordCount - 1);19        int extraSpaces = spaceCount % (wordCount - 1);20 21        String separator = " ".repeat(spacesPerGap);22        String trailingSpaces = " ".repeat(extraSpaces);23 24        return String.join(separator, words) + trailingSpaces;25    }26}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

This method provides the most control over the process by handling parsing at a low level.

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.
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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String reorderSpaces(String text) {6        List<String> words = new ArrayList<>();7        int spaceCount = 0;8        int n = text.length();9        int i = 0;10        while (i < n) {11            if (text.charAt(i) == ' ') {12                spaceCount++;13                i++;14            } else {15                int j = i;16                while (j < n && text.charAt(j) != ' ') {17                    j++;18                }19                words.add(text.substring(i, j));20                i = j;21            }22        }23 24        int wordCount = words.size();25        if (wordCount == 1) {26            return words.get(0) + " ".repeat(spaceCount);27        }28 29        int spacesPerGap = spaceCount / (wordCount - 1);30        int extraSpaces = spaceCount % (wordCount - 1);31 32        StringBuilder sb = new StringBuilder();33        sb.append(String.join(" ".repeat(spacesPerGap), words));34        sb.append(" ".repeat(extraSpaces));35        36        return sb.toString();37    }38}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String reorderSpaces(String text) {4    int cnt = 0;5    for (char c : text.toCharArray()) {6      if (c == ' ') {7        ++cnt;8      }9    }10    String[] words = text.split("\\s+");11    List<String> res = new ArrayList<>();12    for (String w : words) {13      if (!"".equals(w)) {14        res.add(w);15      }16    }17    int m = res.size() - 1;18    if (m == 0) {19      return res.get(0) + " ".repeat(cnt);20    }21    String ans = String.join(" ".repeat(cnt / m), res);22    ans += " ".repeat(cnt % m);23    return ans;24  }25}

1class Solution:2    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)

1class Solution {2public:3  string reorderSpaces(string text) {4    int spaces = ranges ::count(text, ' ');5    auto words = split(text);6    if (words.size() == 1) {7      return words[0] + string(spaces, ' ');8    }9    int cnt = spaces / (words.size() - 1);10    int mod = spaces % (words.size() - 1);11    string result = join(words, string(cnt, ' '));12    result += string(mod, ' ');13    return result;14  }15 16private:17  vector<string> split(const string &text) {18    vector<string> words;19    istringstream stream(text);20    string word;21    while (stream >> word) {22      words.push_back(word);23    }24    return words;25  }26  string join(const vector<string> &words, const string &separator) {27    ostringstream result;28    for (size_t i = 0; i < words.size(); ++i) {29      result << words[i];30      if (i < words.size() - 1) {31        result << separator;32      }33    }34    return result.str();35  }36};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  String reorderSpaces(String text) {4    int cnt = 0;5    for (char c : text.toCharArray()) {6      if (c == ' ') {7        ++cnt;8      }9    }10    String[] words = text.split("\\s+");11    List<String> res = new ArrayList<>();12    for (String w : words) {13      if (!"".equals(w)) {14        res.add(w);15      }16    }17    int m = res.size() - 1;18    if (m == 0) {19      return res.get(0) + " ".repeat(cnt);20    }21    String ans = String.join(" ".repeat(cnt / m), res);22    ans += " ".repeat(cnt % m);23    return ans;24  }25}

1class Solution:2    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)

1class Solution {2public:3  string reorderSpaces(string text) {4    int spaces = ranges ::count(text, ' ');5    auto words = split(text);6    if (words.size() == 1) {7      return words[0] + string(spaces, ' ');8    }9    int cnt = spaces / (words.size() - 1);10    int mod = spaces % (words.size() - 1);11    string result = join(words, string(cnt, ' '));12    result += string(mod, ' ');13    return result;14  }15 16private:17  vector<string> split(const string &text) {18    vector<string> words;19    istringstream stream(text);20    string word;21    while (stream >> word) {22      words.push_back(word);23    }24    return words;25  }26  string join(const vector<string> &words, const string &separator) {27    ostringstream result;28    for (size_t i = 0; i < words.size(); ++i) {29      result << words[i];30      if (i < words.size() - 1) {31        result << separator;32      }33    }34    return result.str();35  }36};

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.