Rearrange Words in a Sentence #7 Most Asked

Medium

2 views

Topics:

Strings

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

Try coding it in LeetCode

Rearrange Words in a Sentence #7 Most Asked

Medium

Expedia Group

2 views

Topics:

Strings

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input sentence string?
Can the input sentence be empty or null?
Will the input sentence only contain words and spaces, or might there be punctuation or other special characters?
How should I handle leading/trailing spaces or multiple spaces between words?
Is case sensitivity important when comparing the lengths of the words?

Brute Force Solution

Approach

The brute force approach to rearranging words involves trying every possible order and combination. We explore all permutations of the words and check each one to see if it meets the sentence's length constraint. This is like trying every single possible arrangement until we find the correct one.

Here's how the algorithm would work step-by-step:

First, list all possible ways to arrange the words in the sentence.
Then, for each arrangement, check if the first word is the shortest.
Capitalize the first letter of the shortest word.
Make sure the other words are lowercase.
Go through each arrangement and see if the total length of the sentence is correct by adding spaces in between.
Keep track of all the arrangements that work.
Finally, pick any valid arrangement from the list.

Code Implementation

import itertools

def rearrange_words_brute_force(text):
    words = text.split()
    shortest_length = float('inf')
    shortest_word = None

    for word in words:
        if len(word) < shortest_length:
            shortest_length = len(word)
            shortest_word = word

    possible_arrangements = list(itertools.permutations(words))
    valid_arrangements = []

    for arrangement in possible_arrangements:
        # Check if the first word in the arrangement is the shortest.
        if len(arrangement[0]) == shortest_length:

            valid_arrangements.append(arrangement)

    best_arrangement = None
    # Store the length to avoid recalculating.
    best_arrangement_length = float('inf')
    for arrangement in valid_arrangements:
        current_length = 0
        is_sorted = True
        for word in arrangement:
            if len(word) < current_length:
                is_sorted = False
                break
            current_length = len(word)

        #We save only the arrangement with the smallest words
        if is_sorted:
            arrangement_length = sum(len(word) for word in arrangement)
            if arrangement_length < best_arrangement_length:
                best_arrangement = arrangement
                best_arrangement_length = arrangement_length

    if best_arrangement:
        return ' '.join(best_arrangement)
    else:
        return text

Big(O) Analysis

Time Complexity

O(n! * n^2) – The brute force approach involves generating all possible permutations of the n words in the sentence, which takes O(n!) time. For each permutation, we iterate through all words to find the shortest word (O(n)). We then capitalize the first word and lowercase the remaining words, which takes O(n) operations. Finally, we check if the length of the rearranged sentence matches the original length by adding spaces, taking O(n) time to account for placing spaces. Therefore, the total time complexity is O(n! * (n + n + n)), which simplifies to O(n! * n^2).

Space Complexity

O(N * N!) – The algorithm generates all permutations of the words, which requires storing up to N! arrangements, where N is the number of words. Each arrangement stores a copy of the original words, contributing O(N) space per permutation. Additionally, storing all valid arrangements before picking one requires O(N * N!) space since we need to keep track of potentially N! arrangements, each of size N. Therefore, the overall auxiliary space complexity is O(N * N!).

Optimal Solution

Approach

The best way to rearrange the words is to sort them based on their lengths first. Then, we rebuild the sentence word by word, ensuring that shorter words come before longer ones, capitalizing the first word and converting the rest to lowercase.

Here's how the algorithm would work step-by-step:

First, split the input sentence into individual words.
Record the original capitalization of the first word because we'll need it later.
Convert all words to lowercase so that sorting isn't affected by capitalization.
Sort the words based on their length, shortest to longest.
Capitalize the first word in the sorted list, restoring the original capitalization from the second step.
Join the words back together into a single sentence, with spaces in between.
Return the rearranged sentence.

Code Implementation

def rearrange_words_in_sentence(text):
    words = text.lower().split()

    # Sort words by their lengths
    words.sort(key=len)

    # Capitalize the first word
    first_word = words[0]
    words[0] = first_word[0].upper() + first_word[1:]

    # Join the words back into a sentence
    rearranged_sentence = ' '.join(words)

    return rearranged_sentence

Big(O) Analysis

Time Complexity

O(n log n) – Let n be the number of words in the input sentence. Splitting the sentence into words takes O(n) time. Converting the words to lowercase also takes O(n) time since we iterate through each word. Sorting the words based on their length using an efficient algorithm like merge sort or quicksort takes O(n log n) time. Joining the words back together takes O(n) time. The dominant operation is sorting, therefore the overall time complexity is O(n log n).

Space Complexity

O(N) – The space complexity is dominated by the creation of a list to hold the individual words after splitting the input sentence. This list stores a copy of each word, leading to a space requirement proportional to the total number of words, N, in the input sentence. We also store the original capitalization of the first word, which takes constant space. Therefore, the auxiliary space used is primarily determined by the list of words, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input string	Return an empty string to avoid processing null or empty input
Input string with only spaces	Trim leading/trailing spaces and return an empty string if only spaces remain
Input string with a single word	Capitalize the first letter of the word and return it
Input string with multiple words of the same length	Maintain original order of words having equal lengths during sorting
Input string with leading or trailing spaces between words	Trim extra spaces between words after splitting into words to ensure correct word length calculation
Very long input string containing many words, potential memory issues	Use efficient data structures and algorithms to minimize memory consumption
Input string with punctuation marks attached to words	Remove or handle punctuation marks before word length calculation and sorting
Input string with mixed case words	Convert all words to lowercase except for the first word after rearrangement

Empty input string

How to Handle:

Return an empty string to avoid processing null or empty input

Input string with only spaces

How to Handle:

Trim leading/trailing spaces and return an empty string if only spaces remain

Input string with a single word

How to Handle:

Capitalize the first letter of the word and return it

Input string with multiple words of the same length

How to Handle:

Maintain original order of words having equal lengths during sorting

Input string with leading or trailing spaces between words

How to Handle:

Trim extra spaces between words after splitting into words to ensure correct word length calculation

Very long input string containing many words, potential memory issues

How to Handle:

Use efficient data structures and algorithms to minimize memory consumption

Input string with punctuation marks attached to words

How to Handle:

Remove or handle punctuation marks before word length calculation and sorting

Input string with mixed case words

How to Handle:

Convert all words to lowercase except for the first word after rearrangement