LeetCode 1451 - Rearrange Words in a Sentence

Difficulty: 🟡 Medium
Topics: String, Sorting

Solution

Problem Understanding

The problem gives us a sentence where words are separated by single spaces, the very first character of the sentence is uppercase, and all remaining characters are lowercase. We must rearrange the words so that they appear in increasing order of word length.

If two words have the same length, we must preserve their original relative order from the input sentence. This requirement is important because it means the sort must behave stably. We are not free to arbitrarily reorder equal-length words.

After rearranging the words, the output sentence must still follow the same formatting rules:

The first word must begin with an uppercase letter.
All remaining letters must be lowercase.

In other words, we need to normalize the sentence, sort the words by length while preserving ties, and then reconstruct the sentence with proper capitalization.

For example, consider:

"Keep calm and code on"

The word lengths are:

Word	Length
Keep	4
calm	4
and	3
code	4
on	2

After sorting by length while preserving original order among equal-length words:

on and keep calm code

Then we capitalize the first character:

"On and keep calm code"

The constraints allow the sentence length to reach 10^5, which means we should avoid unnecessarily expensive operations. A solution with O(n log n) complexity is perfectly acceptable because sorting dominates the runtime. A quadratic approach could become too slow for large inputs.

Several edge cases are important:

A sentence containing only one word.
Multiple words with identical lengths.
Very short words such as "a" or "i".
Cases where the first word becomes much later in the reordered sentence.
Large inputs where efficiency matters.

The problem guarantees that:

Words are separated by exactly one space.
The first letter of the sentence is uppercase.
All other letters are lowercase.

Because of these guarantees, parsing becomes straightforward.

Approaches

Brute Force Approach

A brute force strategy would repeatedly search for the shortest unused word and append it to the result. We could scan all remaining words each time to find the minimum length word that has not yet been selected.

For example:

Find the shortest unused word.
Append it to the answer.
Mark it as used.
Repeat until all words are processed.

This works because each iteration selects the next correct word in sorted order. However, every selection requires scanning the remaining words, leading to quadratic complexity.

If there are k words, each selection may scan up to k words, giving roughly:

O(k^2)

With large inputs, this becomes inefficient.

Optimal Approach

The key observation is that the problem is fundamentally a stable sorting problem.

We can:

Convert the entire sentence to lowercase.
Split the sentence into words.
Perform a stable sort by word length.
Capitalize the first character of the final sentence.

Modern sorting implementations are efficient and stable. Python's built-in sort() is stable, and Go's sort.SliceStable() preserves relative ordering for equal keys.

Since sorting dominates the work, the complexity becomes:

O(k log k)

which is efficient for the given constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k²)	O(k)	Repeatedly scans remaining words to find shortest
Optimal	O(k log k)	O(k)	Uses stable sorting by word length

Here, k represents the number of words in the sentence.

Algorithm Walkthrough

Convert the entire sentence to lowercase.

This simplifies capitalization handling later. Since the final output requires only the first letter of the entire sentence to be uppercase, converting everything to lowercase first guarantees consistent formatting. 2. Split the sentence into a list of words.

Since the input guarantees single spaces between words, a normal split operation cleanly extracts every word. 3. Perform a stable sort using word length as the sorting key.

The sort compares words based on len(word). Stability is important because equal-length words must remain in their original order. 4. Join the sorted words back into a sentence.

After sorting, we reconstruct the sentence using spaces. 5. Capitalize the first character of the resulting sentence.

The problem requires the final sentence to begin with an uppercase letter. Since everything else is already lowercase, capitalizing the first character completes the formatting.

Why it works

The algorithm works because stable sorting guarantees that words with equal lengths maintain their original ordering. Sorting by word length ensures the words appear in increasing order of size. Converting the sentence to lowercase first and capitalizing only the first character afterward guarantees the required output formatting.

Python Solution

class Solution:
    def arrangeWords(self, text: str) -> str:
        words = text.lower().split()

        words.sort(key=len)

        result = " ".join(words)

        return result.capitalize()

The implementation begins by converting the sentence to lowercase and splitting it into individual words.

words = text.lower().split()

This guarantees uniform casing and simplifies later processing.

Next, the words are sorted by length:

words.sort(key=len)

Python's built-in sorting algorithm is stable, which means words with identical lengths automatically preserve their original order.

After sorting, the words are joined back into a sentence:

result = " ".join(words)

Finally, the first character is capitalized:

return result.capitalize()

Since the entire sentence was previously converted to lowercase, this produces exactly the required formatting.

Go Solution

package main

import (
	"sort"
	"strings"
)

func arrangeWords(text string) string {
	words := strings.Fields(strings.ToLower(text))

	sort.SliceStable(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})

	result := strings.Join(words, " ")

	return strings.ToUpper(result[:1]) + result[1:]
}

The Go implementation follows the same overall strategy as the Python version.

Go does not provide a direct stable sort for slices using keys, so we use:

sort.SliceStable(...)

This preserves the relative order of equal-length words.

String capitalization is handled manually because Go strings are immutable and there is no direct equivalent of Python's capitalize() that exactly matches the required behavior.

The input guarantees that the sentence contains at least one character, so accessing result[:1] is safe.

Worked Examples

Example 1

Input:

"Leetcode is cool"

Step 1: Convert to lowercase

Original	Lowercase
Leetcode is cool	leetcode is cool

Step 2: Split into words

Index	Word	Length
0	leetcode	8
1	is	2
2	cool	4

Step 3: Stable sort by length

Sorted Position	Word	Length
0	is	2
1	cool	4
2	leetcode	8

Step 4: Join words

"is cool leetcode"

Step 5: Capitalize first letter

"Is cool leetcode"

Final output:

"Is cool leetcode"

Example 2

Input:

"Keep calm and code on"

Step 1: Lowercase

"keep calm and code on"

Step 2: Split words

Index	Word	Length
0	keep	4
1	calm	4
2	and	3
3	code	4
4	on	2

Step 3: Stable sort

Sorted Position	Word	Length
0	on	2
1	and	3
2	keep	4
3	calm	4
4	code	4

Notice that:

keep, calm, and code all have length 4
Their original order is preserved

Step 4: Join

"on and keep calm code"

Step 5: Capitalize

"On and keep calm code"

Final output:

"On and keep calm code"

Example 3

Input:

"To be or not to be"

Step 1: Lowercase

"to be or not to be"

Step 2: Split words

Index	Word	Length
0	to	2
1	be	2
2	or	2
3	not	3
4	to	2
5	be	2

Step 3: Stable sort

Sorted Position	Word	Length
0	to	2
1	be	2
2	or	2
3	to	2
4	be	2
5	not	3

Step 4: Join

"to be or to be not"

Step 5: Capitalize

"To be or to be not"

Final output:

"To be or to be not"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k log k)	Stable sorting of `k` words dominates runtime
Space	O(k)	Storage for split words and reconstructed sentence

The most expensive operation is sorting. Stable sorting algorithms generally require O(k log k) time. Splitting and joining the sentence are both linear operations.

The extra space comes from storing the list of words and the reconstructed output string.

Test Cases

solution = Solution()

# Provided examples
assert solution.arrangeWords("Leetcode is cool") == "Is cool leetcode"  # basic example
assert solution.arrangeWords("Keep calm and code on") == "On and keep calm code"  # stable ordering
assert solution.arrangeWords("To be or not to be") == "To be or to be not"  # many equal lengths

# Single word
assert solution.arrangeWords("Hello") == "Hello"  # single word input

# All words same length
assert solution.arrangeWords("Cat dog pig") == "Cat dog pig"  # order unchanged

# Already sorted by length
assert solution.arrangeWords("A bb ccc dddd") == "A bb ccc dddd"  # no rearrangement needed

# Reverse sorted lengths
assert solution.arrangeWords("Longest tiny me") == "Me tiny longest"  # complete reordering

# Repeated words
assert solution.arrangeWords("Code code code") == "Code code code"  # identical words

# Very short words
assert solution.arrangeWords("I am a") == "I a am"  # small word handling

# Mixed equal-length groups
assert solution.arrangeWords("Four score and seven years ago") == "And ago four score seven years"  # multiple groups

Test	Why
`"Leetcode is cool"`	Validates basic sorting
`"Keep calm and code on"`	Validates stable ordering
`"To be or not to be"`	Tests repeated equal lengths
`"Hello"`	Tests single-word input
`"Cat dog pig"`	Tests unchanged ordering
`"A bb ccc dddd"`	Tests already sorted input
`"Longest tiny me"`	Tests reverse ordering
`"Code code code"`	Tests repeated identical words
`"I am a"`	Tests very short words
`"Four score and seven years ago"`	Tests multiple equal-length groups

Edge Cases

One important edge case is a sentence containing only one word. A careless implementation might incorrectly modify capitalization or attempt unnecessary sorting logic. In this implementation, splitting produces a one-element list, sorting leaves it unchanged, and capitalization preserves the correct format.

Another important case occurs when many words share the same length. The problem specifically requires maintaining the original relative order for equal-length words. An unstable sorting algorithm could reorder these words incorrectly. Using Python's stable sort() and Go's sort.SliceStable() guarantees correct behavior.

A third edge case involves capitalization handling. Since the input begins with an uppercase letter, directly sorting without normalization could produce incorrect casing in the middle of the sentence. By converting the entire sentence to lowercase first and capitalizing only the first character at the end, the implementation guarantees consistent formatting regardless of how the words are rearranged.