Rearrange Words in a Sentence

Medium
1216.

Rearrange Words in a Sentence

Rearrange Words in a Sentence is a medium coding problem on strings and sorting, asked in Amazon and Microsoft interviews.

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^5
  • text begins with an uppercase letter, followed by lowercase letters and single spaces
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @return {string}
 */
var arrangeWords = function(text) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • text begins with an uppercase letter, followed by lowercase letters and single spaces

Hints for Rearrange Words in a Sentence

  1. Hint 1

    Lowercase the first letter before rearranging, and capitalise the new first letter afterwards.

  2. Hint 2

    You need a sort by length that keeps equal-length words in their original order — a stable sort.

  3. 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

  1. Lowercase the first character of text and split it into words.
  2. Sort the words by length, breaking ties by original position (or use a stable sort).
  3. 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's usort, C#'s Array.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