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.

Examples

Example 1

1
2
3
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

1
2
3
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.

Solution

Method 1 – Count and Distribute Spaces

Intuition

Count the total spaces and words, then distribute the spaces evenly between words, putting any extra spaces at the end.

Approach

  1. Count the total number of spaces in the string.
  2. Split the string into words.
  3. If only one word, put all spaces at the end.
  4. Otherwise, distribute spaces evenly between words, and put the remainder at the end.
  5. Join the words with the calculated number of spaces.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string reorderSpaces(string text) {
        int spaces = count(text.begin(), text.end(), ' ');
        vector<string> words;
        istringstream ss(text);
        string w;
        while (ss >> w) words.push_back(w);
        int n = words.size();
        string sep(n == 1 ? 0 : spaces / (n-1), ' ');
        string ans;
        for (int i = 0; i < n; ++i) {
            if (i) ans += sep;
            ans += words[i];
        }
        ans += string(n == 1 ? spaces : spaces % (n-1), ' ');
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import (
    "strings"
)
func reorderSpaces(text string) string {
    spaces := strings.Count(text, " ")
    words := strings.Fields(text)
    n := len(words)
    sep := ""
    if n > 1 {
        sep = strings.Repeat(" ", spaces/(n-1))
    }
    ans := strings.Join(words, sep)
    if n == 1 {
        ans += strings.Repeat(" ", spaces)
    } else {
        ans += strings.Repeat(" ", spaces%(n-1))
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import java.util.*;
class Solution {
    public String reorderSpaces(String text) {
        int spaces = 0;
        for (char c : text.toCharArray()) if (c == ' ') spaces++;
        String[] words = text.trim().split("\\s+");
        int n = words.length;
        String sep = n == 1 ? "" : " ".repeat(spaces / (n-1));
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            if (i > 0) ans.append(sep);
            ans.append(words[i]);
        }
        int rem = n == 1 ? spaces : spaces % (n-1);
        ans.append(" ".repeat(rem));
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    fun reorderSpaces(text: String): String {
        val spaces = text.count { it == ' ' }
        val words = text.trim().split(Regex("\\s+"))
        val n = words.size
        val sep = if (n == 1) "" else " ".repeat(spaces / (n-1))
        val ans = StringBuilder()
        for ((i, w) in words.withIndex()) {
            if (i > 0) ans.append(sep)
            ans.append(w)
        }
        val rem = if (n == 1) spaces else spaces % (n-1)
        ans.append(" ".repeat(rem))
        return ans.toString()
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def reorderSpaces(self, text: str) -> str:
        spaces = text.count(' ')
        words = text.split()
        n = len(words)
        if n == 1:
            return words[0] + ' ' * spaces
        sep, rem = divmod(spaces, n-1)
        return (' ' * sep).join(words) + ' ' * rem
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn reorder_spaces(text: String) -> String {
        let spaces = text.chars().filter(|&c| c == ' ').count();
        let words: Vec<&str> = text.split_whitespace().collect();
        let n = words.len();
        let sep = if n == 1 { 0 } else { spaces / (n-1) };
        let mut ans = words.join(&" ".repeat(sep));
        let rem = if n == 1 { spaces } else { spaces % (n-1) };
        ans.push_str(&" ".repeat(rem));
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    reorderSpaces(text: string): string {
        const spaces = text.split('').filter(c => c === ' ').length;
        const words = text.trim().split(/\s+/);
        const n = words.length;
        const sep = n === 1 ? '' : ' '.repeat(Math.floor(spaces / (n-1)));
        let ans = words.join(sep);
        const rem = n === 1 ? spaces : spaces % (n-1);
        ans += ' '.repeat(rem);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since we scan and build the result in linear time.
  • 🧺 Space complexity: O(n), for storing the words and the result.