#1451

Medium

LeetCode Problem Workspace

Rearrange Words in a Sentence

Rearrange words in a sentence by their length, maintaining original order for words of equal size for consistent output.

string sorting

Problem Statement

Given a sentence string consisting of words separated by single spaces, where the sentence starts with a capital letter and contains only lowercase letters otherwise, rearrange all words so that they are sorted by increasing length. Maintain the original relative order for words with identical lengths, and ensure the reconstructed sentence starts with a capital letter.

Your task is to return the newly formed sentence after sorting by word length, preserving original word order in tie cases, and applying proper capitalization rules for the first word while keeping the rest lowercase.

Examples

Example 1

Input: text = "Leetcode is cool"

Output: "Is cool leetcode"

There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4. Output is ordered by length and the new first word starts with capital letter.

Example 2

Input: text = "Keep calm and code on"

Output: "On and keep calm code"

Output is ordered as follows: "On" 2 letters. "and" 3 letters. "keep" 4 letters in case of tie order by position in original text. "calm" 4 letters. "code" 4 letters.

Example 3

Input: text = "To be or not to be"

Output: "To be or to be not"

Example details omitted.

Constraints

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

Solution Approach

Split and Track Original Positions

Break the input sentence into a list of words while storing each word's original index. This allows stable sorting later to preserve order when word lengths are equal.

Sort by Length with Stable Tie-Breaking

Sort the word list primarily by word length and secondarily by original index. This ensures that shorter words come first and that ties respect the initial order from the input sentence.

Reconstruct the Sentence with Proper Capitalization

Join the sorted words with single spaces. Capitalize the first character of the first word and convert all remaining words to lowercase to match the required output format.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) where n is the number of words due to sorting, and space complexity is O(n) for storing words and their indices. The approach handles up to 10^5 characters efficiently while maintaining stable ordering for ties.

What Interviewers Usually Probe

Asks how you maintain original word order when lengths are equal.
Checks if your solution handles capitalization correctly after sorting.
Probes understanding of stable sorting and tracking original indices.

Common Pitfalls or Variants

Common pitfalls

Forgetting to preserve original order for words of the same length.
Not capitalizing the first word or altering case of other words incorrectly.
Using inefficient methods that exceed time limits for large sentences.

Follow-up variants

Rearranging words in descending length order instead of ascending.
Ignoring capitalization rules and returning all lowercase sentence.
Sorting words alphabetically only when lengths are equal instead of using original positions.

FAQ

What is the main pattern in Rearrange Words in a Sentence?

The problem uses the String plus Sorting pattern, sorting words by length while tracking original positions.

How do you handle words of equal length?

Words of equal length should retain their original order from the input sentence to ensure stable sorting.

Should the first word always be capitalized?

Yes, after sorting, capitalize the first character of the first word and convert all other words to lowercase.

Can the sentence contain punctuation or multiple spaces?

No, the sentence contains only letters with single spaces between words, and the first word starts with a capital letter.

What is the time complexity of this approach?

Time complexity is O(n log n) due to sorting words, and space complexity is O(n) for storing words and indices.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

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

Continue Practicing

#1433 check if a string can break another string #1418 display table of food orders in a restaurant #1366 rank teams by votes