Problem Description

You are given a sentence text which is a string of space-separated words with the following properties:

• The first letter of the sentence is uppercase
• Words are separated by single spaces

Your task is to rearrange the words in the sentence based on their length in increasing order. If two or more words have the same length, they should maintain their original relative order from the input sentence.

After rearranging, the output should follow the same format as the input - the first letter should be uppercase and words should be separated by single spaces.

For example, if the input is "Leetcode is cool", the words have lengths [8, 2, 4]. After sorting by length while preserving the original order for same-length words, we get "is" (length 2), "cool" (length 4), "Leetcode" (length 8). The final output would be "Is cool leetcode" with the first letter capitalized.

The solution approach converts the first word to lowercase before sorting (to handle the capital letter uniformly), sorts all words by their length using a stable sort, then capitalizes the first letter of the result before joining the words back together with spaces.

Intuition

The main challenge in this problem is handling the capitalization requirement while sorting words by length. If we sort the words directly, the first word (which starts with a capital letter) might not end up in the correct position due to case sensitivity in string comparisons.

The key insight is that we need to normalize all words to the same case before sorting to ensure fair comparison. Since only the first letter of the sentence needs to be capitalized (not necessarily the first letter of the first word in the original sentence), we can:

1. Convert the first word to lowercase to put all words on equal footing
2. Sort the words purely by their length
3. After sorting, capitalize the first letter of whatever word ends up first

Python's sort() function is stable, meaning that when multiple elements have the same key (in this case, length), they maintain their original relative order. This naturally handles the requirement that words of the same length should appear in their original order.

The approach is elegant because it separates the concerns: first handle the sorting logic without worrying about capitalization, then apply the capitalization rule to the final result. This way, we avoid complex comparison functions or having to track which word was originally first.

Using key=len in the sort operation directly compares words by their length, making the solution both readable and efficient.

Learn more about Sorting patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Split the sentence into words: We use text.split() to break the sentence into a list of individual words. This automatically handles the single space separation.

2. Normalize the first word: We convert the first word to lowercase using words[0] = words[0].lower(). This is crucial because the first word might have a capital letter that could affect its sorting position. By converting it to lowercase, we ensure all words are compared fairly by length alone.

3. Sort words by length: We use words.sort(key=len) which sorts the list in-place. The key=len parameter tells Python to use the length of each word as the sorting criterion. Since Python's sort is stable, words with the same length will maintain their original relative order from the input.

4. Capitalize the new first word: After sorting, we apply the capitalization rule to whatever word is now at position 0 using words[0] = words[0].title(). The title() method capitalizes the first letter and lowercases the rest, which handles both cases where the new first word was originally lowercase or had mixed case.

5. Join the words back: Finally, we use " ".join(words) to combine the sorted words back into a single string with spaces between them.

The time complexity is O(n log n) due to the sorting operation, where n is the number of words. The space complexity is O(n) for storing the list of words.

Example Walkthrough

Let's walk through the solution with the example "The quick brown fox":

Step 1: Split into words

• Input: "The quick brown fox"
• After splitting: ["The", "quick", "brown", "fox"]

Step 2: Normalize the first word

• Convert "The" to lowercase: ["the", "quick", "brown", "fox"]
• This ensures the capital 'T' doesn't affect sorting

Step 3: Analyze word lengths

• "the": length 3
• "quick": length 5
• "brown": length 5
• "fox": length 3

Step 4: Sort by length (stable sort)

• Words of length 3: "the", "fox" (maintain original order)
• Words of length 5: "quick", "brown" (maintain original order)
• After sorting: ["the", "fox", "quick", "brown"]

Step 5: Capitalize the new first word

• Capitalize "the" → "The"
• Result: ["The", "fox", "quick", "brown"]

Step 6: Join with spaces

• Final output: "The fox quick brown"

Notice how "the" and "fox" both have length 3, but "the" appears before "fox" in the final result because it came first in the original sentence. Similarly, "quick" and "brown" both have length 5 and maintain their original order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

• Splitting the text into words takes O(n) where n is the length of the input string
• Converting the first word to lowercase takes O(m) where m is the length of the first word
• Sorting the words by length takes O(k log k) where k is the number of words. In the worst case, if all words are single characters, k could be O(n), making this O(n log n)
• Converting the first word to title case takes O(m) where m is the length of the first word
• Joining the words back together takes O(n)
• Overall: O(n) + O(m) + O(k log k) + O(m) + O(n) = O(n log n) (dominated by the sorting operation)

Space Complexity: O(n)

• The words list stores all words from the input text, requiring O(n) space where n is the total length of the input string
• The sorting operation may use additional O(k) space where k is the number of words (for the sorting algorithm's internal operations)
• The final joined string also requires O(n) space
• Overall: O(n) space complexity

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Original Capitalization

One of the most common mistakes is forgetting that the first word in the input is capitalized, which affects its sorting position. If you don't normalize it to lowercase before sorting, it might end up in the wrong position.

Incorrect approach:

def arrangeWords(self, text: str) -> str:
    words = text.split()
    words.sort(key=len)  # Wrong! "Leetcode" will sort differently than "leetcode"
    words[0] = words[0].capitalize()
    return " ".join(words)

Why it fails: Capital letters have different ASCII values than lowercase letters. While this doesn't directly affect length-based sorting, the original capitalized word might have inconsistent casing when moved to a different position.

Solution: Always convert the first word to lowercase before sorting to ensure consistent comparison.

2. Using title() Instead of capitalize()

While both methods can work, using title() can cause issues if there are words with mixed cases or special characters.

Potential issue:

words[0] = words[0].title()  # Can cause problems with words like "don't" → "Don'T"

Better approach:

words[0] = words[0].capitalize()  # Safer: "don't" → "Don't"

3. Not Preserving Stable Order

Using a custom sorting function that doesn't maintain stability will break the requirement that same-length words maintain their original order.

Incorrect approach:

# Using a sorting method that isn't guaranteed to be stable
words = sorted(words, key=lambda x: (len(x), x))  # Wrong! This adds secondary sorting

Solution: Use Python's built-in sort() or sorted() with only the length as the key, as they guarantee stable sorting.

4. Modifying the Original Word Case

Some solutions might accidentally lowercase all words or fail to preserve the original casing of words (except the first one).

Incorrect approach:

def arrangeWords(self, text: str) -> str:
    words = text.lower().split()  # Wrong! This lowercases everything
    words.sort(key=len)
    words[0] = words[0].capitalize()
    return " ".join(words)

Why it fails: If the input is "Leetcode is COOL", the output should preserve "COOL" as uppercase (except when it becomes the first word). The above approach would incorrectly change it to "cool".