Skip to main content
Talentd

Rearrange Words in a Sentence - Solution & Explanation

MediumStringSorting14 min readAsked at: Microsoft, Expedia
Practice this problem

Problem Statement

Given a sentence text (A sentence is a string of space-separated words) in the following format:

  • First letter is in upper case.
  • Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

 

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: 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"
Explanation: 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"

 

Constraints:

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

Approach Overview

Problem Overview: You receive a sentence where the first word is capitalized and the rest are lowercase. Rearrange the words in ascending order of their lengths while keeping words with the same length in their original relative order. The final sentence must start with a capitalized word and the rest must remain lowercase.

Approach 1: Sort Words by Length Using Built-in Sort (O(n log n) time, O(n) space)

Split the sentence into words, convert the entire string to lowercase, and sort the words by their length. Most standard library sorts (like Python's sorted or Java's Arrays.sort) are stable, meaning words with the same length preserve their original order automatically. After sorting, capitalize the first word and join the array back into a sentence using spaces. This approach relies on built-in sorting utilities and straightforward string manipulation. Time complexity is O(n log n) due to sorting the words, and space complexity is O(n) for storing the split words and reconstructed sentence.

Approach 2: Custom Sort by Length and Capitalize First (O(n log n) time, O(n) space)

Instead of relying on a language's built-in sort, implement your own sorting logic based on word length. First convert the sentence to lowercase and split it into an array. Apply a custom comparison function that orders words by len(word). Any stable algorithm such as merge sort keeps words of equal length in their original order, satisfying the problem requirement. After sorting, capitalize the first character of the first word and rebuild the sentence using a join operation. This method demonstrates explicit control over the comparison logic and is useful when implementing sorting from scratch during interviews. Complexity remains O(n log n) time and O(n) auxiliary space.

Recommended for interviews: The built-in sort solution is what most interviewers expect. It shows you recognize that a stable length-based sort solves the ordering constraint with minimal code. Mention that stability preserves relative order for equal-length words. Implementing a custom comparator or stable sort is helpful when the interviewer wants deeper discussion about sorting algorithms or internal mechanics, but the built-in approach demonstrates practical problem solving quickly.

Approach 1: Sort Words by Length Using Built-in Sort

This approach involves splitting the sentence into individual words and then using a stable sort method to arrange the words by their length. Languages typically have built-in sort functionalities which can use a custom key to sort based on the length of each word. The first word in the result then needs to be capitalized to maintain the sentence format.

The C solution involves splitting the string into words using strtok, storing them in an array, and sorting them using qsort. The custom comparator sorts by word length. After sorting, convert the first letter of the first word to uppercase and concatenate the words back into the sentence.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n log n) where n is the number of words due to sorting.
Space complexity: O(n) for storing the words.

Try this approach in the editor →

Approach 2: Custom Sort by Length and Capitalize First

This approach uses a custom method to first sort the words by length and then recreate the sentence. The main idea is to use a stable sorting algorithm that will retain the original order of words with the same length, and then to capitalize the first word using string manipulation methods available in each programming language.

Similar to the C solution in Approach 1, but clearly emphasizes separating the word capitalization step into a separate function. The words are extracted and stored in an array, sorted using qsort, and concatenated back with attention to capitalizing the first word.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n log n) for sorting.
Space complexity: O(n), mainly for the storage of words.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScriptPHP

Python

Java

C++

Go

TypeScript

JavaScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort Words by Length Using Built-in Sort

Time complexity: O(n log n) where n is the number of words due to sorting.
Space complexity: O(n) for storing the words.

Custom Sort by Length and Capitalize First

Time complexity: O(n log n) for sorting.
Space complexity: O(n), mainly for the storage of words.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort Words by Length Using Built-in SortO(n log n)O(n)Best general solution. Simple implementation using stable library sort.
Custom Sort by Length and Capitalize FirstO(n log n)O(n)When implementing sorting logic manually or explaining stable sorting behavior in interviews.

Video Solution

Rearrange Words in a Sentence • Fraz • 3,170 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Rearrange Words in a Sentence easy or hard?
The problem is usually rated Medium because it combines multiple small requirements: stable ordering, string normalization, and proper capitalization. The core idea—sorting by word length—is straightforward, but missing stability or formatting details can lead to incorrect results.
Rearrange Words in a Sentence Python/Java solution
In Python, split the sentence, convert to lowercase, and call sorted(words, key=len) since Python's Timsort is stable. In Java, split the string and use Arrays.sort with a comparator comparing word length. After sorting, capitalize the first word and join the words using spaces.
How to solve Rearrange Words in a Sentence in O(n)?
The typical solution uses O(n log n) sorting. An O(n) approach is possible by grouping words using bucket sort based on their lengths. Iterate through the words, store them in buckets indexed by length, and then rebuild the sentence from smallest to largest bucket while preserving insertion order. This works when maximum word length is reasonably bounded.
What is the best approach for Rearrange Words in a Sentence?
The most practical approach is to split the sentence into words, convert everything to lowercase, and perform a stable sort based on word length. After sorting, capitalize the first word and join the words back into a sentence. Because standard library sorts are stable, words with the same length keep their original order. This solution runs in O(n log n) time and O(n) space.
Is Rearrange Words in a Sentence asked at Google/Amazon/Meta?
String manipulation and sorting problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests understanding of stable sorting, string processing, and careful formatting of output. Variants of ordering words or tokens by specific properties are common interview exercises.
What data structure is used in Rearrange Words in a Sentence?
The solution mainly uses arrays or lists to store words after splitting the sentence. A sorting algorithm orders the words by length. Some optimized variations use buckets (arrays of lists) keyed by word length to achieve near-linear processing.
What is the time complexity of Rearrange Words in a Sentence?
The dominant operation is sorting the words by their length. If there are k words in the sentence, sorting takes O(k log k) time, which is typically represented as O(n log n) relative to input size. Splitting and joining the string both take linear time. Space complexity is O(n) for storing the words.

Ready to solve this problem?

Practice Rearrange Words in a Sentence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring