<p>Given a sentence&nbsp;<code>text</code> (A&nbsp;<em>sentence</em>&nbsp;is a string of space-separated words) in the following format:</p>

<ul>
	<li>First letter is in upper case.</li>
	<li>Each word in <code>text</code> are separated by a single space.</li>
</ul>

<p>Your task is to rearrange the words in text such that&nbsp;all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.</p>

<p>Return the new text&nbsp;following the format shown above.</p>

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

<pre>
<strong>Input:</strong> text = &quot;Leetcode is cool&quot;
<strong>Output:</strong> &quot;Is cool leetcode&quot;
<strong>Explanation: </strong>There are 3 words, &quot;Leetcode&quot; of length 8, &quot;is&quot; of length 2 and &quot;cool&quot; of length 4.
Output is ordered by length and the new first word starts with capital letter.
</pre>

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

<pre>
<strong>Input:</strong> text = &quot;Keep calm and code on&quot;
<strong>Output:</strong> &quot;On and keep calm code&quot;
<strong>Explanation: </strong>Output is ordered as follows:
&quot;On&quot; 2 letters.
&quot;and&quot; 3 letters.
&quot;keep&quot; 4 letters in case of tie order by position in original text.
&quot;calm&quot; 4 letters.
&quot;code&quot; 4 letters.
</pre>

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

<pre>
<strong>Input:</strong> text = &quot;To be or not to be&quot;
<strong>Output:</strong> &quot;To be or to be not&quot;
</pre>

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

<ul>
	<li><code>text</code> begins with a capital letter and then contains lowercase letters and single space between words.</li>
	<li><code>1 &lt;= text.length &lt;= 10^5</code></li>
</ul>

class Solution {
public:
    string arrangeWords(string text) {
        int n = text.size(); // Get the size of the input string
        
        // Step 1: Convert the first character to lowercase
        // Since the first word in the sentence starts with an uppercase letter, we need to make it lowercase.
        text[0] = tolower(text[0]);

        // Step 2: Split the text into words using stringstream
        // We'll use stringstream to easily extract words separated by spaces.
        vector<string> words; // To store the individual words
        stringstream ss(text); // Stringstream initialized with the input text
        string word;
        
        // Extract words separated by spaces and store them in the vector
        while (ss >> word) {
            words.push_back(word); // Add each word to the vector
        }

        // Step 3: Sort the words by their lengths using stable_sort
        // We use stable_sort to maintain the relative order of words with the same length.
        stable_sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size(); // Sort words based on their length
        });

        // Step 4: Join the sorted words into a single sentence
        string result; // String to store the final sentence
        for (const string& w : words) {
            result += w + " "; // Append each word followed by a space
        }

        // Remove the last unnecessary space at the end of the sentence
        result.pop_back(); // The last word will have a trailing space that needs to be removed

        // Step 5: Capitalize the first character of the resulting sentence
        result[0] = toupper(result[0]); // Capitalize the first letter of the final sentence

        return result; // Return the rearranged sentence
    }
};


21800