{x}
blog image

Rearrange Words in a Sentence

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

Solution Explanation

This problem requires rearranging the words in a sentence based on their lengths. Words of the same length should maintain their original order. The first word in the rearranged sentence must start with a capital letter.

The solution employs a straightforward approach:

  1. Split the sentence: The input sentence is split into individual words using the space character as a delimiter.

  2. Lowercase the first word: The first word is converted to lowercase to ensure consistent sorting.

  3. Sort the words: The sort (or stable_sort in C++) function is used to arrange the words based on their length. Critically, we use stable_sort or a stable sorting mechanism to maintain the relative order of words with the same length. This ensures that the original order is preserved when length is equal. The sorting key is simply the length of each word (len in Python, String::length in Java, etc.).

  4. Capitalize the first word: After sorting, the first word is re-capitalized to match the original sentence format.

  5. Join the words: Finally, the sorted words are joined back together with spaces to form the rearranged sentence.

Time and Space Complexity Analysis

Time Complexity: O(N log N), dominated by the sorting step. N is the number of words in the sentence. Sorting algorithms generally have O(N log N) time complexity in the average and worst cases. All other operations (splitting, joining, capitalization) have linear time complexity O(N).

Space Complexity: O(N). In the worst case, the space required to store the words in a list or array is proportional to the number of words in the input sentence. This excludes the input string itself.

Code Explanation (Python)

The Python code showcases a concise implementation:

class Solution:
    def arrangeWords(self, text: str) -> str:
        words = text.split()  #splits the text into words using space as delimiter
        words[0] = words[0].lower() #converts the first word to lowercase
        words.sort(key=len)  #sorts the words based on length using the len function as a key. This is a stable sort which is important for maintaining the order of words with equal length
        words[0] = words[0].title() #Capitalizes the first letter of the first word.
        return " ".join(words) #joins the words into a string with spaces in between.

The code in other languages follows a similar structure, adapting the syntax and libraries as needed to perform the same operations. For example, Java uses Arrays.sort with a custom Comparator, while C++ uses stable_sort with a lambda function for comparison. The core logic remains consistent across all implementations.