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

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6
7
8

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

1
2

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

Solution

Method 1 – Stable Sort by Length

Intuition

Sort the words by their length, keeping the original order for words of the same length. Then, format the result so the first word is capitalized and the rest are lowercase.

Approach

  1. Split the sentence into words, making the first word lowercase.
  2. Sort the words by length using a stable sort.
  3. Capitalize the first word of the result and join the words with spaces.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <algorithm>
class Solution {
public:
    string arrangeWords(string text) {
        vector<string> words;
        istringstream ss(text);
        string w;
        while (ss >> w) words.push_back(w);
        words[0][0] = tolower(words[0][0]);
        stable_sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });
        words[0][0] = toupper(words[0][0]);
        string ans;
        for (int i = 0; i < words.size(); ++i) {
            if (i) ans += ' ';
            ans += words[i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import (
    "strings"
    "unicode"
    "sort"
)
func arrangeWords(text string) string {
    words := strings.Fields(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, " ")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import java.util.*;
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);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun arrangeWords(text: String): String {
        val words = text.split(" ").toMutableList()
        words[0] = words[0].lowercase()
        val sorted = words.sortedWith(compareBy({ it.length }))
        val res = sorted.toMutableList()
        res[0] = res[0].replaceFirstChar { it.uppercase() }
        return res.joinToString(" ")
    }
}
1
2
3
4
5
6
7

class Solution:
    def arrangeWords(self, text: str) -> str:
        words = text.split()
        words[0] = words[0].lower()
        words = sorted(words, key=len)
        words[0] = words[0].capitalize()
        return ' '.join(words)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn arrange_words(text: String) -> String {
        let mut words: Vec<String> = text.split_whitespace().map(|s| s.to_lowercase()).collect();
        words[0] = words[0].to_lowercase();
        words.sort_by_key(|w| w.len());
        if let Some(first) = words.get_mut(0) {
            if let Some(c) = first.get_mut(0..1) {
                *c = c.to_uppercase().to_string();
            }
        }
        words.join(" ")
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    arrangeWords(text: string): string {
        let words = text.split(' ');
        words[0] = words[0].toLowerCase();
        words = words.sort((a, b) => a.length - b.length);
        words[0] = words[0][0].toUpperCase() + words[0].slice(1);
        return words.join(' ');
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the text, since sorting is stable and the number of words is proportional to n.
  • 🧺 Space complexity: O(n), for storing the words and the result.