Rearrange Words in a Sentence — Problem & Solution
Rearrange Words in a Sentence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Rearrange Words in a Sentence is a medium coding problem on strings and sorting, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Sorting
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sentence text is a list of words separated by single spaces; its first letter is uppercase and every other letter is lowercase.
Rearrange the words in increasing order of length. Words of the same length keep the order they had in text. Return the new sentence in the same format: first letter uppercase, all other letters lowercase, single spaces between words.
Example 1
Input: text = "Keep calm and code on"
Output: On and keep calm code
Explanation: Lengths 2, 3, 4, 4, 4 — the three 4-letter words keep their original order.
Example 2
Input: text = "Kairo is fun"
Output: Is fun kairo
Example 3
Input: text = "Hi"
Output: Hi
Constraints
1 <= text.length <= 10^5text begins with an uppercase letter, followed by lowercase letters and single spaces
Hints for Rearrange Words in a Sentence
Hint 1
Lowercase the first letter before rearranging, and capitalise the new first letter afterwards.
Hint 2
You need a sort by length that keeps equal-length words in their original order — a stable sort.
Hint 3
If your language's sort is not stable, sort by the pair (length, original index), or bucket the words by length.
How to solve Rearrange Words in a Sentence
The task is a stable sort of the words by length, plus fixing the capital letter at both ends of the process.
Approach
- Lowercase the first character of
textand split it into words. - Sort the words by length, breaking ties by original position (or use a stable sort).
- Join them with single spaces and uppercase the first character.
Why it works
A stable sort orders by length and leaves words of equal length in their input order, which is exactly the required tie rule. Lowercasing the first word before sorting makes sure the capital does not travel with it, and capitalising after joining puts it on whichever word now comes first.
Complexity
- Time —
O(n log n) for the sort (O(n) with length buckets) - Space —
O(n)
Pitfalls
- Forgetting to lowercase the original first word, so a capital letter appears mid-sentence.
- Using an unstable sort (C's
qsort, PHP 7'susort, C#'sArray.Sort) without an index tie-break. - Comparing words alphabetically on ties — the rule is original order.
Reference solution
Python
def arrangeWords(text: str) -> str:
words = text.lower().split(" ")
words.sort(key=len)
s = " ".join(words)
return s[0].upper() + s[1:]Java
public static String arrangeWords(String text) {
String[] words = text.toLowerCase().split(" ");
Arrays.sort(words, (a, b) -> a.length() - b.length());
String s = String.join(" ", words);
return Character.toUpperCase(s.charAt(0)) + s.substring(1);
}C++
string arrangeWords(string text) {
for (char& c : text) if (c >= 'A' && c <= 'Z') c = (char)(c - 'A' + 'a');
vector<string> words;
stringstream ss(text);
string w;
while (ss >> w) words.push_back(w);
stable_sort(words.begin(), words.end(), [](const string& a, const string& b) { return a.size() < b.size(); });
string s;
for (size_t i = 0; i < words.size(); i++) {
if (i > 0) s += ' ';
s += words[i];
}
s[0] = (char)(s[0] - 'a' + 'A');
return s;
}JavaScript
var arrangeWords = function(text) {
var words = text.toLowerCase().split(" ");
var idx = [];
for (var i = 0; i < words.length; i++) idx.push(i);
idx.sort(function(a, b) { return words[a].length - words[b].length || a - b; });
var out = [];
for (var j = 0; j < idx.length; j++) out.push(words[idx[j]]);
var s = out.join(" ");
return s.charAt(0).toUpperCase() + s.substring(1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sorting Algorithms