Rearrange Words in a Sentence

Problem Description

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.

Key Insights

• The first letter of the result must be capitalized.
• Words should be sorted primarily by their lengths.
• Words with the same length should maintain their original relative order.

Space and Time Complexity

Time Complexity: O(n log n) - where n is the number of words due to sorting. Space Complexity: O(n) - for storing the words during processing.

Solution

To solve the problem, we can follow these steps:

1. Split the input string into individual words.
2. Use a stable sorting algorithm to sort the words based on their lengths. Python's built-in sort is stable, which means it will maintain the order of words that have the same length.
3. Capitalize the first word of the sorted list.
4. Join the words back into a single string with spaces.

We will utilize the list data structure to hold the words and the sorting function to reorder them.

Code Solutions