Rearrange Words in a Sentence
MedPrompt
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
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
textto lowercase. - Split the modified
textinto an array of strings,words, using space as the delimiter. - Sort the
wordsarray usingArrays.sort()with a customComparator. The comparator(a, b) -> Integer.compare(a.length(), b.length())sorts the words by their length in ascending order. - Join the sorted
wordsarray 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 wordsWis very large compared to the total number of charactersN.
A more efficient approach for this problem is to use Bucket Sort. Since the sorting key is the length of the words, we can group words into "buckets" based on their length. This avoids the comparison-based sorting overhead of O(W log W). By iterating through the buckets in order of length, we can construct the final sentence.
Algorithm
- Convert the first character of the input
textto lowercase. - Split the
textinto an array ofwords. - Initialize a
TreeMap<Integer, List<String>>to store words grouped by length. TheTreeMapwill ensure that we can process the word lengths in ascending order. - Iterate through the
wordsarray:- For each
word, get its lengthlen. - Add the
wordto the list associated withlenin the map. If no list exists forlen, create a new one first.
- For each
- Initialize a
StringBuilderfor the result. - Iterate through the values (the
List<String>) of theTreeMap.- For each list of words, append each word and a space to the
StringBuilder.
- For each list of words, append each word and a space to the
- Remove the final trailing space.
- Capitalize the first letter of the
StringBuilder. - Return the resulting string.
Walkthrough
The core idea is to use a data structure where each key corresponds to a word length and the value is a list of all words having that length. By using a structure that keeps keys sorted, like a TreeMap, we can achieve the desired order.
First, we preprocess the input text by converting the first letter to lowercase and splitting it into words. Then, we iterate through each word, find its length, and add it to the corresponding list in the TreeMap. Since we add words to the end of the list, their original relative order is preserved, satisfying the tie-breaking rule.
After all words are placed in their respective buckets, we iterate through the TreeMap. Because TreeMap processes keys in ascending order, we naturally get the lists of words sorted by length. We concatenate the words from these lists to form the new sentence, add spaces, and finally, capitalize the first letter of the result.
import java.util.ArrayList;import java.util.List;import java.util.Map;import java.util.TreeMap; class Solution { public String arrangeWords(String text) { // 1. Lowercase the first letter and split into words String[] words = text.toLowerCase().split(" "); // 2. Group words by length into a TreeMap to keep lengths sorted Map<Integer, List<String>> map = new TreeMap<>(); for (String word : words) { int len = word.length(); map.computeIfAbsent(len, k -> new ArrayList<>()).add(word); } // 3. Build the result string from the map StringBuilder result = new StringBuilder(); for (List<String> wordList : map.values()) { for (String word : wordList) { result.append(word).append(" "); } } // Remove the last space result.setLength(result.length() - 1); // 4. Capitalize the first letter result.setCharAt(0, Character.toUpperCase(result.charAt(0))); return result.toString(); }}Complexity
Time
O(N). While the `TreeMap` implementation has a time complexity of `O(N + W log K)` (where `W` is the number of words and `K` is the number of unique lengths), a more optimized version of Bucket Sort using an array of lists would achieve `O(N + L_max)`, where `L_max` is the maximum word length. Since `L_max` is at most `N`, this simplifies to `O(N)`, which is linear and asymptotically faster than the comparison sort approach.
Space
O(N), where `N` is the length of the input string. The `words` array, the `TreeMap`, and the `StringBuilder` each require space proportional to the total number of characters in the input.
Trade-offs
Pros
Asymptotically more efficient than comparison-based sorting, especially when the number of words is large.
The logic of grouping by a key (length) is a common and powerful pattern.
Cons
The implementation can be slightly more complex than a direct sort.
The
TreeMapversion has a logarithmic factor (O(W log K)), making its performance similar to comparison sort in some cases, though often with better constant factors.
Solutions
Solution
/** * @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(" ");};class Solution {public String arrangeWords(String text) { String[] words = text.split(" "); words[0] = words[0].toLowerCase(); Arrays.sort(words, Comparator.comparingInt(String : : length)); words[0] = words[0].substring(0, 1).toUpperCase() + words[0].substring(1); return String.join(" ", words); }}class Solution { public: string arrangeWords ( string text ) { vector < string > words ; stringstream ss ( text ); string t ; while ( ss >> t ) { words . push_back ( t ); } words [ 0 ][ 0 ] = tolower ( words [ 0 ][ 0 ]); stable_sort ( words . begin (), words . end (), []( const string & a , const string & b ) { return a . size () < b . size (); }); string ans = "" ; for ( auto & s : words ) { ans += s + " " ; } ans . pop_back (); ans [ 0 ] = toupper ( ans [ 0 ]); return ans ; } };class Solution: def arrangeWords(self, text: str) -> str: words = text . split() words[0] = words[0]. lower() words . sort(key=len) words[0] = words[0]. title() return " " . join(words)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.