Watch 10 video solutions for Rearrange Words in a Sentence, a medium level problem involving String, Sorting. This walkthrough by Fraz has 3,164 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |