Rearrange Words in a Sentence solution and explanation
9 more videos on this problem
Rearrange Words in a SentenceFraz · 9:28 · 3K views
LeetCode 1451 Rearrange Words in a SentenceNaresh Gupta · 5:07 · 1K views
1451. Rearrange Words in a Sentence | Leetcode MediumChhavi Bansal · 11:35 · 1K views
1451 Rearrange Words in a Sentence || Weekly Contest 189 || LEETCODEcode Explainer · 7:19 · 1K views
Leetcode 1451 Rearrange Words in a sentence (Java)TheAnalyticGuy · 4:36 · 613 views
Rearrange Words in a Sentence (Leetcode 1451)Coding Interviews · 17:02 · 394 views
1451. Rearrange Words in a Sentence (Leetcode Medium)Programming Live with Larry · 3:57 · 315 views
Leetcode 1451 Rearrange Words in a SentenceMaxMing · 1:48 · 128 views
LeetCode 1451 Rearrange Words in a Sentence - Explained 2 Approaches To Solve This ProblemAlgorithmicIQ · 18:36 · 84 views
LeetCode 1451 | Rearrange Words in a Sentence | OpHaxor SolutionAlgorithms & Programming Interview Prep · 10:25 · 76 views
The problem
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
textare 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:
textbegins 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.
def rearrange_words(text):
words = text.split()
words.sort(key=len)
words[0] = words[0].capitalize()
return ' '.join(words)
text = "Leetcode is cool"
print(rearrange_words(text))import java.util.*;
public class Main {
public static String rearrangeWords(String text) {
String[] words = text.split(" ");
Arrays.sort(words, (a, b) -> a.length() - b.length());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < words.length; i++) {
if (i == 0) {
sb.append(Character.toUpperCase(words[i].charAt(0)));
sb.append(words[i].substring(1));
} else {
sb.append(words[i]);
}
if (i < words.length - 1) {
sb.append(" ");
}
}
return sb.toString();
}
public static void main(String[] args) {
String text = "Leetcode is cool";
System.out.println(rearrangeWords(text));
}
}#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
void capitalize(std::string &word) {
if (!word.empty()) {
word[0] = toupper(word[0]);
}
}
std::string rearrangeWords(const std::string &text) {
std::istringstream iss(text);
std::vector<std::string> words;
std::string word;
while (iss >> word) {
words.push_back(word);
}
stable_sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
return a.length() < b.length();
});
capitalize(words[0]);
std::ostringstream oss;
for (size_t i = 0; i < words.size(); ++i) {
if (i != 0) oss << " ";
oss << words[i];
}
return oss.str();
}
int main() {
std::string text = "Leetcode is cool";
std::string result = rearrangeWords(text);
std::cout << result << std::endl;
return 0;
}function rearrangeWords(text) {
let words = text.split(' ');
words.sort((a, b) => a.length - b.length);
words[0] = words[0].charAt(0).toUpperCase() + words[0].slice(1);
return words.join(' ');
}
let text = "Leetcode is cool";
console.log(rearrangeWords(text));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (strlen(*(const char **)a) - strlen(*(const char **)b));
}
void capitalize_first_letter(char *word) {
if (word[0] >= 'a' && word[0] <= 'z') {
word[0] = word[0] - 32;
}
}
char *rearrangeWords(char *text) {
char *words[1000];
int count = 0;
char *token = strtok(text, " ");
while (token != NULL) {
words[count++] = token;
token = strtok(NULL, " ");
}
qsort(words, count, sizeof(char *), compare);
char *result = (char *)malloc(strlen(text) + 1);
result[0] = '\0';
for (int i = 0; i < count; i++) {
if (i == 0) {
capitalize_first_letter(words[i]);
}
strcat(result, words[i]);
if (i < count - 1) {
strcat(result, " ");
}
}
return result;
}
int main() {
char text[] = "Leetcode is cool";
char *result = rearrangeWords(text);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Linq;
class Program {
static string RearrangeWords(string text) {
var words = text.Split(' ');
words = words.OrderBy(word => word.Length).ToArray();
words[0] = char.ToUpper(words[0][0]) + words[0].Substring(1);
return string.Join(" ", words);
}
static void Main() {
string text = "Leetcode is cool";
Console.WriteLine(RearrangeWords(text));
}
}The Python solution splits the sentence using split(), sorts it using sort() with a custom key that sorts by length, capitalizes the first word, and joins the words back with spaces.
Time complexity: O(n log n) because of sorting.
Space complexity: O(n) for storing split words.
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.
def rearrange_sentence(text):
words = text.split()
words.sort(key=len)
words[0] = words[0].capitalize()
return ' '.join(words)
text = "Leetcode is cool"
print(rearrange_sentence(text))import java.util.Arrays;
public class Solution {
public static String rearrangeSentence(String text) {
String[] words = text.split(" ");
Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
words[0] = Character.toUpperCase(words[0].charAt(0)) + words[0].substring(1).toLowerCase();
return String.join(" ", words);
}
public static void main(String[] args) {
String text = "Leetcode is cool";
System.out.println(rearrangeSentence(text));
}
}#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
void capitalize(std::string &word) {
if (!word.empty()) {
word[0] = toupper(word[0]);
}
}
std::string rearrangeSentence(std::string text) {
std::istringstream stream(text);
std::vector<std::string> words;
std::string temp;
while (stream >> temp) {
words.push_back(temp);
}
stable_sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
return a.size() < b.size();
});
capitalize(words[0]);
std::ostringstream os;
for (size_t i = 0; i < words.size(); ++i) {
if (i != 0) os << " ";
os << words[i];
}
return os.str();
}
int main() {
std::string text = "Leetcode is cool";
std::cout << rearrangeSentence(text) << std::endl;
return 0;
}function rearrangeSentence(text) {
let words = text.split(' ');
words.sort((a, b) => a.length - b.length);
words[0] = words[0].charAt(0).toUpperCase() + words[0].slice(1);
return words.join(' ');
}
let text = "Leetcode is cool";
console.log(rearrangeSentence(text));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare_length(const void *a, const void *b) {
return (strlen(*(const char **)a) - strlen(*(const char **)b));
}
void capitalize_first_char(char *word) {
if (word != NULL && word[0] != '\0' && word[0] >= 'a' && word[0] <= 'z') {
word[0] = word[0] - 32;
}
}
char *rearrangeSentence(char *text) {
char *words[1000];
int current_index = 0;
char *token = strtok(text, " ");
while (token != NULL) {
words[current_index++] = token;
token = strtok(NULL, " ");
}
qsort(words, current_index, sizeof(char *), compare_length);
capitalize_first_char(words[0]);
char *result = (char *)malloc(strlen(text) + 1);
result[0] = '\0';
for (int i = 0; i < current_index; ++i) {
strcat(result, words[i]);
if (i < current_index - 1) {
strcat(result, " ");
}
}
return result;
}
int main() {
char text[] = "Leetcode is cool";
char *result = rearrangeSentence(text);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Linq;
class Program {
static string RearrangeSentence(string text) {
string[] words = text.Split(' ');
words = words.OrderBy(w => w.Length).ToArray();
words[0] = char.ToUpper(words[0][0]) + words[0].Substring(1);
return string.Join(" ", words);
}
static void Main() {
string text = "Leetcode is cool";
Console.WriteLine(RearrangeSentence(text));
}
}This Python solution segments the sentence into words via split(), orders them by length with sort() using a key, corrects capitalization of the first word, and recombines to form the sentence.
Time complexity: O(n log n) due to sorting.
Space complexity: O(n) from the list of words.
Approach 3: Default Approach
function arrangeWords(text: string): string {
let words: string[] = text.split(' ');
words[0] = words[0].toLowerCase();
words.sort((a, b) => a.length - b.length);
words[0] = words[0].charAt(0).toUpperCase() + words[0].slice(1);
return words.join(' ');
}func arrangeWords(text string) string {
words := strings.Split(text, " ")
words[0] = strings.ToLower(words[0])
sort.SliceStable(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
words[0] = strings.Title(words[0])
return strings.Join(words, " ")
}class Solution {
/**
* @param String $text
* @return String
*/
function arrangeWords($text) {
$text = lcfirst($text);
$arr = explode(' ', $text);
for ($i = 0; $i < count($arr); $i++) {
$hashtable[$i] = strlen($arr[$i]);
}
asort($hashtable);
$key = array_keys($hashtable);
$rs = [];
for ($j = 0; $j < count($key); $j++) {
array_push($rs, $arr[$key[$j]]);
}
return ucfirst(implode(' ', $rs));
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort Words by Length Using Built-in Sort | Time complexity: |
| Custom Sort by Length and Capitalize First | Time complexity: |
| Default Approach | – |
Complexity analysis
| 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. |
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.