Rearrange Words in a Sentence: Stable Sort by Length
LeetCode Rearrange Words in a Sentence (problem 1451) asks you to take a sentence, split it into words, and rearrange those words in ascending order of length. If two words have the same length, they should keep their original relative order. The first letter of the result must be capitalized, and all other letters must be lowercase.
Why this problem matters
This problem is a clean exercise in stable sorting. In many sorting problems you only care about the final order, but here the tie-breaking rule matters: same-length words must preserve their original positions. That makes it a perfect test of whether you truly understand what "stable sort" means, and when to rely on it. The capitalization step at the end is a small string manipulation detail that trips people up in interviews if they forget it.
The key insight
The entire problem reduces to three operations: split, stable sort, and rejoin. You lowercase the sentence first so capitalization does not interfere with sorting. Then you sort the words by length using a stable sort, which guarantees that words of equal length stay in their original order. Finally, you capitalize the first letter of the joined result.
Python's built-in sorted() function is stable, so you do not need any special comparator or secondary key. Just sort by len and you are done.
The solution
def arrange_words(text: str) -> str:
words = text.lower().split()
words.sort(key=len)
result = " ".join(words)
return result[0].upper() + result[1:]
The function starts by converting the entire input to lowercase with text.lower(). This strips the capital letter from the first word so it does not affect sorting. Then split() breaks the sentence into a list of words.
The words.sort(key=len) call sorts the list in place by word length. Since Python's sort is stable, words with the same length remain in their original order. After sorting, " ".join(words) glues the words back together with spaces.
The last line capitalizes the first character of the result. result[0].upper() converts the first character to uppercase, and result[1:] appends the rest unchanged.
Python's sorted() and list.sort() are both stable. This means you can always rely on them to preserve the relative order of elements that compare as equal. Any time a problem says "preserve original order for ties," stable sort is your tool.
Visual walkthrough
Step 1: Lowercase and split the sentence into words
Convert the entire sentence to lowercase, then split on spaces. This removes the original capitalization so sorting is clean.
Step 2: Sort words by their length (ascending)
Use a stable sort so words of equal length stay in their original order. Python's sorted() is stable by default.
Step 3: Why stable sort? Same-length words keep original order
"one" and "two" both have length 3. A stable sort guarantees "one" stays before "two" because it appeared first in the input.
Step 4: Capitalize the first letter of the result
Only the very first word gets its first letter capitalized. All other words remain lowercase.
Step 5: Join with spaces and return "Is cool leetcode"
Join the sorted words with single spaces. The problem guarantees no leading, trailing, or double spaces in the output.
The walkthrough above traces the algorithm on the input "Leetcode is cool." First you lowercase and split to get ["leetcode", "is", "cool"]. Then you sort by length to get ["is", "cool", "leetcode"]. Finally you capitalize the first letter to produce "Is cool leetcode."
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Stable sort | O(n log n) | O(n) |
The sort dominates the runtime. Splitting and joining are both O(n) where n is the length of the input string. The sort operates on the number of words, call it w, so it is O(w log w). Since w is at most n (every character could be a one-letter word), the overall time is O(n log n).
Space is O(n) for the list of words and the result string. No additional data structures are needed beyond what the sort itself uses.
The building blocks
1. Stable sort by a key function
words.sort(key=len)
Sorting by a key function is one of Python's most useful patterns. You pass a function that extracts the comparison value from each element. Here, len returns the length of each word, so the sort orders words from shortest to longest. Because the sort is stable, equal-length words keep their original order.
2. String capitalization after transformation
result = " ".join(words)
return result[0].upper() + result[1:]
A common pattern when a problem requires specific capitalization is to normalize everything to lowercase first, do your transformations, and then apply the capitalization rule at the very end. This avoids edge cases where an uppercase letter in the middle of the process could cause incorrect behavior.
Edge cases
- Single word. The input has only one word. It gets lowercased and then re-capitalized, returning essentially the same word with proper casing.
- All words the same length. The stable sort preserves the original order entirely. The output is the same as the input, just with only the first letter capitalized.
- Already sorted by length. No reordering happens. The algorithm handles this correctly without any special case.
From understanding to recall
This problem is simple in concept, but the details matter. Forgetting to lowercase before sorting, or forgetting to capitalize after joining, are the two most common mistakes. When you review this problem, focus on the three-step pipeline: lowercase and split, stable sort by length, capitalize and join. If you can reproduce that pipeline from memory, you own this problem. Spaced repetition helps you keep these small but critical details fresh so they are automatic when you see a similar problem in an interview.
Related posts
- Group Anagrams - Another string problem involving grouping and sorting
- Sort Colors - Sorting with constraints, building intuition for stable vs unstable sorts
- Custom Sort String - Another custom ordering problem on strings
Patterns like stable sort by a key function appear across many problems. CodeBricks uses spaced repetition to help you internalize these building blocks so you can recognize and apply them instantly. Instead of re-learning the pattern each time, you build lasting recall through targeted practice.