We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rearrange Words in a Sentence

Number: 1561

Difficulty: Medium

Paid? No

Companies: Expedia

Problem Description

Given a sentence where the first letter is capitalized and words are separated by single spaces, rearrange the sentence so that the words are ordered in increasing order of their lengths. If two words have the same length, their original order is maintained. Additionally, the output sentence should also start with a capital letter, with the rest of the characters in lowercase.

Key Insights

  • Split the sentence into words.
  • Convert all words to lowercase initially to ease processing.
  • Use a stable sort by word length to preserve the original order for words with equal lengths.
  • After sorting, capitalize the first letter of the first word before rejoining the words into the final sentence.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of words. Space Complexity: O(n) for storing the list of words.

Solution

The algorithm works by:

  1. Converting the input sentence to lowercase and splitting it into words.
  2. Sorting the words using a stable sort with the key being the length of the word. This ensures that words with the same length maintain their original order.
  3. Capitalizing the first letter of the first word in the sorted list to adhere to the sentence formatting requirement.
  4. Joining the words back together with a space between them to form the final rearranged sentence.

Data structures used include a list/array to hold the words, and the sorting algorithm is used to reorganize the words by their lengths.

Code Solutions

def rearrangeWords(text):
    # Convert text to lower case and split into words
    words = text.lower().split()
    # Sort the words using stable sort, comparing by length
    sorted_words = sorted(words, key=len)
    # Capitalize the first letter of the first word
    sorted_words[0] = sorted_words[0].capitalize()
    # Join the words to form the final sentence
    return ' '.join(sorted_words)

# Example usage:
print(rearrangeWords("Leetcode is cool"))   # Output: "Is cool leetcode"
print(rearrangeWords("Keep calm and code on"))  # Output: "On and keep calm code"
print(rearrangeWords("To be or not to be"))    # Output: "To be or to be not"
← Back to All Questions