<p>You are given a string <code>text</code> 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&#39;s guaranteed that <code>text</code> <strong>contains at least one word</strong>.</p>

<p>Rearrange the spaces so that there is an <strong>equal</strong> number of spaces between every pair of adjacent words and that number is <strong>maximized</strong>. If you cannot redistribute all the spaces equally, place the <strong>extra spaces at the end</strong>, meaning the returned string should be the same length as <code>text</code>.</p>

<p>Return <em>the string after rearranging the spaces</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;  this   is  a sentence &quot;
<strong>Output:</strong> &quot;this   is   a   sentence&quot;
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot; practice   makes   perfect&quot;
<strong>Output:</strong> &quot;practice   makes   perfect &quot;
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text.length &lt;= 100</code></li>
	<li><code>text</code> consists of lowercase English letters and <code>&#39; &#39;</code>.</li>
	<li><code>text</code> contains at least one word.</li>
</ul>

class Solution {
public:
    string reorderSpaces(string text) {
        vector<string> words;
        int n = text.size(), spaces = 0;
        string str = "";
        
        text.push_back(' ');
        for(int i = 0; i < n + 1; i++) {
            if(text[i] == ' ') {
                spaces++;
                if(str.size() > 0)
                    words.push_back(str);
                str = "";
            } else {
                str += text[i];
            }
        }
        spaces--;
        text.pop_back();
        
        // cout<<"spaces: "<<spaces<<endl;
        
        int numWords = words.size();
        int spaceBetweenWords = numWords > 1 ? spaces / (numWords - 1) : 0;
        int remainingSpaces = spaces - (spaceBetweenWords * (numWords - 1));
        
        // cout<<"spaceBetweenWords: "<<spaceBetweenWords<<endl;
        
        string spaceStr = "";
        int count = 0;
        while(count < spaceBetweenWords)
            spaceStr += " ", count++;
        
        // cout<<"spaceStr: "<<spaceStr<<"*"<<endl;
        
        // for(string word : words)
        //     cout<<word<<" ";
        // cout<<endl;
        
        string ans = "";
        for(int i = 0; i < numWords; i++) {
            ans = ans + words[i];
            if(i < numWords - 1)
                ans += spaceStr;
        }
        
        if(remainingSpaces > 0) {
            while(remainingSpaces--)
                ans += " ";
        }
        
        return ans;
    }
};
8000