Scale Engineer

Rearrange Words in a Sentence

Med
#1341Time: O(N + W log W), where `N` is the length of the input string `text` and `W` is the number of words. Splitting the string takes `O(N)`. Sorting `W` words takes `O(W log W)`. Joining the words back takes `O(N)`. The overall complexity is dominated by the larger of these terms.Space: O(N), where `N` is the length of the input string `text`. The `words` array requires `O(N)` space to store all the characters. The sorting algorithm might use `O(W)` auxiliary space in the worst case (where `W` is the number of words). The final result string also requires `O(N)` space.1 company
Algorithms
Sorting
Data structures
String
Companies
Expedia

Prompt

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 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^5

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves splitting the sentence into individual words and then sorting them using a custom comparison logic. The standard library's sorting functions are typically stable, which is a key requirement for this problem: words with the same length must maintain their original relative order.

Algorithm

  • Handle the edge case of an empty or null input string.
  • Convert the first character of the input text to lowercase.
  • Split the modified text into an array of strings, words, using space as the delimiter.
  • Sort the words array using Arrays.sort() with a custom Comparator. The comparator (a, b) -> Integer.compare(a.length(), b.length()) sorts the words by their length in ascending order.
  • Join the sorted words array back into a single string, separated by spaces.
  • Capitalize the first character of the resulting string.
  • Return the final string.

Walkthrough

First, we need to handle the capitalization. The original first word, which is capitalized, needs to be converted to lowercase to ensure all words are treated uniformly during sorting. The entire sentence is then split into an array of words.

We then sort this array of words. The primary sorting criterion is the length of the word, in ascending order. Since Java's Arrays.sort() for objects is a stable sort, it automatically handles the tie-breaking rule (maintaining original order) for us. We just need to provide a comparator that compares words based on their length.

After sorting, we join the words back into a single string, separated by spaces. Finally, we format the resulting sentence by capitalizing its first letter.

import java.util.Arrays;import java.util.Comparator; class Solution {    public String arrangeWords(String text) {        // 1. Lowercase the first letter and split into words        String[] words = text.toLowerCase().split(" ");         // 2. Sort the words array based on length.        // Arrays.sort for objects is stable, which handles the tie-breaking rule.        Arrays.sort(words, Comparator.comparingInt(String::length));         // 3. Join the words back into a sentence        String result = String.join(" ", words);         // 4. Capitalize the first letter of the new sentence        if (result.isEmpty()) {            return "";        }        return Character.toUpperCase(result.charAt(0)) + result.substring(1);    }}

Complexity

Time

O(N + W log W), where `N` is the length of the input string `text` and `W` is the number of words. Splitting the string takes `O(N)`. Sorting `W` words takes `O(W log W)`. Joining the words back takes `O(N)`. The overall complexity is dominated by the larger of these terms.

Space

O(N), where `N` is the length of the input string `text`. The `words` array requires `O(N)` space to store all the characters. The sorting algorithm might use `O(W)` auxiliary space in the worst case (where `W` is the number of words). The final result string also requires `O(N)` space.

Trade-offs

Pros

  • Relatively simple to implement using standard library functions.

  • The logic is straightforward and easy to understand.

  • Leverages the stability of the built-in sort to handle the tie-breaking requirement elegantly.

Cons

  • The time complexity of O(W log W) from sorting can be suboptimal if the number of words W is very large compared to the total number of characters N.

Solutions

/** * @param {string} text * @return {string} */ var arrangeWords = function (  text,) {  let arr = text.split(" ");  arr[0] = arr[0].toLocaleLowerCase();  arr.sort((a, b) => a.length - b.length);  arr[0] = arr[0][0].toLocaleUpperCase() + arr[0].substr(1);  return arr.join(" ");};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem