MediumSorting

Rearrange Words in a Sentence

1 approach, code in every language

You are given a sentence: a single-space separated string of words where the first word starts with a capital letter. Rearrange the words in ascending order of their length. When two words have the same length, keep them in their original relative order.

Return the resulting sentence with only the first letter capitalized and every other letter in lowercase.

Example 1

Input: text = "Leetcode is cool"

Output: "Is cool leetcode"

Lengths are is (2), cool (4), leetcode (8), so the order becomes "is cool leetcode" and the first letter is capitalized.

Example 2

Input: text = "Keep calm and code on"

Output: "On and keep calm code"

Sorting by length gives on (2), and (3), then keep, calm, code (all 4) preserved in their original order.

Constraints

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

Stable Sort by Word Length

Lowercase, split into words, stable-sort by length, rejoin, and fix the capitalization.

Loading animation…

Intuition

The problem is a direct sorting task once we normalise case. We lowercase the whole sentence so capitalization does not interfere with the final formatting, then split it into words. Sorting the words by length gives the required ascending order, and using a stable sort keeps words of equal length in their original relative positions, which is exactly the tie-breaking rule. After joining the sorted words back together with single spaces, we only need to capitalize the very first character to produce a properly formatted sentence.

Algorithm walkthrough

1Lowercase the entire sentence so the original capital letter no longer matters.
2Split the lowercased text into individual words on the single spaces.
3Stable-sort the words by ascending length so equal-length words keep their original order.
4Join the sorted words back into one string separated by single spaces.
5Uppercase the first character of the joined string and return it.

Implementation

class Solution:
    def arrangeWords(self, text: str) -> str:
        words = text.lower().split()
        words.sort(key=len)
        result = " ".join(words)
        return result[0].upper() + result[1:]

Time

O(M log M + L)

Space

O(L)

M is the number of words and L the total sentence length. Sorting the words dominates at O(M log M), while lowercasing and joining are linear in L. The word list and result buffer take O(L) space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free