Given a sentence text (A sentence is a string of space-separated words) in the following format:
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^5Problem 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.
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.
Time complexity: O(n log n) where n is the number of words due to sorting.
Space complexity: O(n) for storing the words.
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.
Time complexity: O(n log n) for sorting.
Space complexity: O(n), mainly for the storage of words.
Python
Java
C++
Go
TypeScript
JavaScript
PHP
| Approach | Complexity |
|---|---|
| Sort Words by Length Using Built-in Sort | Time complexity: |
| Custom Sort by Length and Capitalize First | Time complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort Words by Length Using Built-in Sort | O(n log n) | O(n) | Best general solution. Simple implementation using stable library sort. |
| Custom Sort by Length and Capitalize First | O(n log n) | O(n) | When implementing sorting logic manually or explaining stable sorting behavior in interviews. |
Rearrange Words in a Sentence • Fraz • 3,164 views views
Watch 9 more video solutions →Practice Rearrange Words in a Sentence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor