Problem Description

Given a sentence represented as a string text, where words are separated by single spaces and the sentence starts with a capital letter, rearrange the words in the sentence in ascending order by the length of each word. If two words have the same length, maintain their original relative order. The output should be a single string with the following properties:

• The first word starts with a capital letter.
• All other words start with lowercase letters.
• There are no extra spaces at the start or end.

• There is always at least one word in text.
• All words are separated by single spaces only.
• Do not change the words themselves except for capitalization as required.

Thought Process

To solve this problem, the first idea might be to split the sentence into words, sort them by length, and then join them back. However, we also need to handle capitalization: only the first word should be capitalized, and all others should be lowercase at the start. Additionally, we must maintain the original order of words with the same length, which suggests a stable sort is necessary.

The brute-force approach would involve nested loops or manual insertion, but sorting algorithms like sorted() in Python or Arrays.sort() in Java can handle stability for us. The main challenge is to carefully process capitalization after sorting and ensure the sentence is reconstructed correctly.

Solution Approach

Here is a step-by-step breakdown of the algorithm:

1. Split the sentence: Convert the input string text into a list of words using space as the delimiter.
2. Normalize casing: Convert the first word to lowercase since the output requires only the first word to be capitalized at the end.
3. Stable sort: Sort the list of words by their length using a stable sorting algorithm. This ensures that words of the same length remain in their original order.
4. Capitalize the first word: After sorting, capitalize the first word of the resulting list.
5. Join the words: Concatenate the words back into a single string, separated by spaces.

We use a stable sort because it preserves the original order of words with equal length, as required by the problem. The capitalization step is handled after sorting to avoid losing information about the original casing.

Example Walkthrough

Input: text = "Leetcode is cool"

• Step 1: Split into words: ["Leetcode", "is", "cool"]
• Step 2: Lowercase first word: ["leetcode", "is", "cool"]
• Step 3: Sort by length (stable sort): ["is", "cool", "leetcode"]
• Step 4: Capitalize first word: ["Is", "cool", "leetcode"]
• Step 5: Join: "Is cool leetcode"

The output sentence starts with a capital letter, and the words are sorted by length, with "is" (2), "cool" (4), and "leetcode" (8).

Time and Space Complexity

• Brute-force approach:
  • Time: O(n^2) if manually inserting words in order of length.
  • Space: O(n) for storing the list of words.
• Optimized (sorting) approach:
  • Time: O(n log n), where n is the number of words, due to sorting.
  • Space: O(n) for the list of words plus output string.

The sorting step dominates the time complexity. The approach is efficient for typical sentence lengths.

Summary

The key to solving this problem efficiently is to:

• Split the sentence into words and normalize casing.
• Use a stable sort to order words by length while maintaining relative order for equal-length words.
• Reapply capitalization to the first word and join the words back into a sentence.

Code Implementation

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

class Solution {
public:
    string arrangeWords(string text) {
        vector<string> words;
        istringstream iss(text);
        string word;
        while (iss >> word) {
            words.push_back(word);
        }
        words[0][0] = tolower(words[0][0]);
        stable_sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });
        words[0][0] = toupper(words[0][0]);
        string result;
        for (int i = 0; i < words.size(); ++i) {
            if (i > 0) result += ' ';
            result += words[i];
        }
        return result;
    }
};
      

class Solution {
    public String arrangeWords(String text) {
        String[] words = text.split(" ");
        words[0] = words[0].toLowerCase();
        Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
        words[0] = words[0].substring(0, 1).toUpperCase() + words[0].substring(1);
        return String.join(" ", words);
    }
}
      

var arrangeWords = function(text) {
    let words = text.split(" ");
    words[0] = words[0].toLowerCase();
    words.sort((a, b) => a.length - b.length);
    words[0] = words[0][0].toUpperCase() + words[0].slice(1);
    return words.join(" ");
};