Rearrange Words in a Sentence - Practice Coding Problems

Rearrange Words in a Sentence - Problem

String Sorting Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: text = "Leetcode is cool"

› Output: "Is leetcode cool"

💡 Note: Words sorted by length: "is"(2), "cool"(4), "Leetcode"(8). Since "cool" and "Leetcode" have different lengths, they keep relative positions within their length groups.

Example 2 — Same Length Words

$ Input: text = "Keep calm and carry on"

› Output: "On and keep calm carry"

💡 Note: Words by length: "On"(2), "and"(3), "Keep"(4), "calm"(4), "carry"(5). "Keep" and "calm" both have length 4, so they maintain original order: "keep" then "calm".

Example 3 — Single Word

$ Input: text = "Hello"

› Output: "Hello"

💡 Note: Only one word, so result is the same with proper capitalization.

Constraints

1 ≤ text.length ≤ 10⁵
text contains only lowercase and uppercase English letters and spaces
All the words in text are separated by a single space
text does not contain any leading or trailing spaces

Visualization

Tap to expand

Understanding the Visualization

Input

Original sentence with proper capitalization

Process

Sort words by length, maintaining original order for ties

Output

Rearranged sentence with first letter capitalized

Key Takeaway

🎯 Key Insight: Use stable sorting to preserve original order for equal-length words while organizing by length

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use stable sorting to maintain original order for words of equal length. The optimal approach splits the sentence, sorts by length while preserving relative positions, then reconstructs with proper capitalization. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Manual Positioning	O(n²)	O(n)	Compare each word with all others to find correct position
Sort with Index Tracking	O(n log n)	O(n)	Create word-index pairs, sort by length then index, reconstruct sentence

Brute Force - Manual Positioning — Algorithm Steps

Split sentence into words
For each word, count how many words should precede it
Place each word at its calculated position
Join words and fix capitalization

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Words

Break sentence into individual words

Calculate Position

For each word, count how many should come before it

Place and Format

Put words in calculated positions and fix capitalization

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char* solution(char* text) {
    char* words[1000];
    int wordCount = 0;
    char* textCopy = malloc(strlen(text) + 1);
    strcpy(textCopy, text);
    
    char* token = strtok(textCopy, " ");
    while (token != NULL) {
        words[wordCount] = malloc(strlen(token) + 1);
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, " ");
    }
    
    char* result[1000];
    for (int i = 0; i < wordCount; i++) {
        int position = 0;
        for (int j = 0; j < wordCount; j++) {
            if (j != i) {
                if (strlen(words[j]) < strlen(words[i]) || 
                   (strlen(words[j]) == strlen(words[i]) && j < i)) {
                    position++;
                }
            }
        }
        result[position] = words[i];
    }
    
    int totalLen = wordCount - 1; // spaces
    for (int i = 0; i < wordCount; i++) {
        totalLen += strlen(result[i]);
    }
    
    char* resultText = malloc(totalLen + 1);
    strcpy(resultText, result[0]);
    for (int i = 1; i < wordCount; i++) {
        strcat(resultText, " ");
        strcat(resultText, result[i]);
    }
    
    for (int i = 0; resultText[i]; i++) {
        resultText[i] = tolower(resultText[i]);
    }
    resultText[0] = toupper(resultText[0]);
    
    free(textCopy);
    return resultText;
}

int main() {
    char text[10000];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    
    char* result = solution(text);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n words, we compare with all other n words

⚠ Quadratic Growth

Space Complexity

O(n)

Store words array and result array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Manual Positioning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler