# Rearrange Words in a Sentence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rearrange-words-in-a-sentence)
Canonical: https://scaleengineer.com/dsa/problems/rearrange-words-in-a-sentence
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** String
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia)
---
## Problem
Given a sentence `text` (A _sentence_ is a string of space-separated words) in the following format:

* First letter is in upper case.
* Each word in `text` are separated by a single space.

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

Return the new text following the format shown above.

**Example 1:**

**Input:** text = "Leetcode is cool"
**Output:** "Is cool leetcode"
**Explanation:** There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

**Example 2:**

**Input:** text = "Keep calm and code on"
**Output:** "On and keep calm code"
**Explanation:** Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

**Example 3:**

**Input:** text = "To be or not to be"
**Output:** "To be or to be not"

**Constraints:**

* `text` begins with a capital letter and then contains lowercase letters and single space between words.
* `1 <= text.length <= 10^5`

# Approaches
## Sorting with a Custom Comparator
This approach involves splitting the sentence into individual words and then sorting them using a custom comparison logic. The standard library's sorting functions are typically stable, which is a key requirement for this problem: words with the same length must maintain their original relative order.
**Time:** O(N + W log W), where `N` is the length of the input string `text` and `W` is the number of words. Splitting the string takes `O(N)`. Sorting `W` words takes `O(W log W)`. Joining the words back takes `O(N)`. The overall complexity is dominated by the larger of these terms. · **Space:** O(N), where `N` is the length of the input string `text`. The `words` array requires `O(N)` space to store all the characters. The sorting algorithm might use `O(W)` auxiliary space in the worst case (where `W` is the number of words). The final result string also requires `O(N)` space.
**Pros:** Relatively simple to implement using standard library functions.; The logic is straightforward and easy to understand.; Leverages the stability of the built-in sort to handle the tie-breaking requirement elegantly.
**Cons:** The time complexity of `O(W log W)` from sorting can be suboptimal if the number of words `W` is very large compared to the total number of characters `N`.
### Explanation
First, we need to handle the capitalization. The original first word, which is capitalized, needs to be converted to lowercase to ensure all words are treated uniformly during sorting. The entire sentence is then split into an array of words.

We then sort this array of words. The primary sorting criterion is the length of the word, in ascending order. Since Java's `Arrays.sort()` for objects is a stable sort, it automatically handles the tie-breaking rule (maintaining original order) for us. We just need to provide a comparator that compares words based on their length.

After sorting, we join the words back into a single string, separated by spaces. Finally, we format the resulting sentence by capitalizing its first letter.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String arrangeWords(String text) {
        // 1. Lowercase the first letter and split into words
        String[] words = text.toLowerCase().split(" ");

        // 2. Sort the words array based on length.
        // Arrays.sort for objects is stable, which handles the tie-breaking rule.
        Arrays.sort(words, Comparator.comparingInt(String::length));

        // 3. Join the words back into a sentence
        String result = String.join(" ", words);

        // 4. Capitalize the first letter of the new sentence
        if (result.isEmpty()) {
            return "";
        }
        return Character.toUpperCase(result.charAt(0)) + result.substring(1);
    }
}
```
### Algorithm
- Handle the edge case of an empty or null input string.
- Convert the first character of the input `text` to lowercase.
- Split the modified `text` into an array of strings, `words`, using space as the delimiter.
- Sort the `words` array using `Arrays.sort()` with a custom `Comparator`. The comparator `(a, b) -> Integer.compare(a.length(), b.length())` sorts the words by their length in ascending order.
- Join the sorted `words` array back into a single string, separated by spaces.
- Capitalize the first character of the resulting string.
- Return the final string.

## Bucket Sort by Word Length
A more efficient approach for this problem is to use Bucket Sort. Since the sorting key is the length of the words, we can group words into "buckets" based on their length. This avoids the comparison-based sorting overhead of `O(W log W)`. By iterating through the buckets in order of length, we can construct the final sentence.
**Time:** O(N). While the `TreeMap` implementation has a time complexity of `O(N + W log K)` (where `W` is the number of words and `K` is the number of unique lengths), a more optimized version of Bucket Sort using an array of lists would achieve `O(N + L_max)`, where `L_max` is the maximum word length. Since `L_max` is at most `N`, this simplifies to `O(N)`, which is linear and asymptotically faster than the comparison sort approach. · **Space:** O(N), where `N` is the length of the input string. The `words` array, the `TreeMap`, and the `StringBuilder` each require space proportional to the total number of characters in the input.
**Pros:** Asymptotically more efficient than comparison-based sorting, especially when the number of words is large.; The logic of grouping by a key (length) is a common and powerful pattern.
**Cons:** The implementation can be slightly more complex than a direct sort.; The `TreeMap` version has a logarithmic factor (`O(W log K)`), making its performance similar to comparison sort in some cases, though often with better constant factors.
### Explanation
The core idea is to use a data structure where each key corresponds to a word length and the value is a list of all words having that length. By using a structure that keeps keys sorted, like a `TreeMap`, we can achieve the desired order.

First, we preprocess the input `text` by converting the first letter to lowercase and splitting it into words. Then, we iterate through each word, find its length, and add it to the corresponding list in the `TreeMap`. Since we add words to the end of the list, their original relative order is preserved, satisfying the tie-breaking rule.

After all words are placed in their respective buckets, we iterate through the `TreeMap`. Because `TreeMap` processes keys in ascending order, we naturally get the lists of words sorted by length. We concatenate the words from these lists to form the new sentence, add spaces, and finally, capitalize the first letter of the result.

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

class Solution {
    public String arrangeWords(String text) {
        // 1. Lowercase the first letter and split into words
        String[] words = text.toLowerCase().split(" ");

        // 2. Group words by length into a TreeMap to keep lengths sorted
        Map<Integer, List<String>> map = new TreeMap<>();
        for (String word : words) {
            int len = word.length();
            map.computeIfAbsent(len, k -> new ArrayList<>()).add(word);
        }

        // 3. Build the result string from the map
        StringBuilder result = new StringBuilder();
        for (List<String> wordList : map.values()) {
            for (String word : wordList) {
                result.append(word).append(" ");
            }
        }

        // Remove the last space
        result.setLength(result.length() - 1);

        // 4. Capitalize the first letter
        result.setCharAt(0, Character.toUpperCase(result.charAt(0)));

        return result.toString();
    }
}
```
### Algorithm
- Convert the first character of the input `text` to lowercase.
- Split the `text` into an array of `words`.
- Initialize a `TreeMap<Integer, List<String>>` to store words grouped by length. The `TreeMap` will ensure that we can process the word lengths in ascending order.
- Iterate through the `words` array:
    - For each `word`, get its length `len`.
    - Add the `word` to the list associated with `len` in the map. If no list exists for `len`, create a new one first.
- Initialize a `StringBuilder` for the result.
- Iterate through the values (the `List<String>`) of the `TreeMap`.
    - For each list of words, append each word and a space to the `StringBuilder`.
- Remove the final trailing space.
- Capitalize the first letter of the `StringBuilder`.
- Return the resulting string.

# Solutions
### JavaScript

```javascript
/** * @param {string} text * @return {string} */ var arrangeWords = function (
  text,
) {
  let arr = text.split(" ");
  arr[0] = arr[0].toLocaleLowerCase();
  arr.sort((a, b) => a.length - b.length);
  arr[0] = arr[0][0].toLocaleUpperCase() + arr[0].substr(1);
  return arr.join(" ");
};

```

### Java

```java
class Solution {
public
  String arrangeWords(String text) {
    String[] words = text.split(" ");
    words[0] = words[0].toLowerCase();
    Arrays.sort(words, Comparator.comparingInt(String : : length));
    words[0] = words[0].substring(0, 1).toUpperCase() + words[0].substring(1);
    return String.join(" ", words);
  }
}

```

### CPP

```cpp
class Solution { public: string arrangeWords ( string text ) { vector < string > words ; stringstream ss ( text ); string t ; while ( ss >> t ) { words . push_back ( t ); } words [ 0 ][ 0 ] = tolower ( words [ 0 ][ 0 ]); stable_sort ( words . begin (), words . end (), []( const string & a , const string & b ) { return a . size () < b . size (); }); string ans = "" ; for ( auto & s : words ) { ans += s + " " ; } ans . pop_back (); ans [ 0 ] = toupper ( ans [ 0 ]); return ans ; } };
```

### Python

```python
class Solution:
    def arrangeWords(self, text: str) -> str: words = text . split() words[0] = words[0]. lower() words . sort(key=len) words[0] = words[0]. title() return " " . join(words)

```