Sorting the Sentence - Practice Coding Problems

Sorting the Sentence - Problem

String Sorting Easy

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.

A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.

For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".

Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.

Input & Output

Example 1 — Basic Case

$ Input: s = "is2 sentence4 This1 T4est 7est"

› Output: "This is sentence T4est 7est"

💡 Note: Sort words by their position digits: This1→position 1, is2→position 2, sentence4→position 4, etc.

Example 2 — Different Order

$ Input: s = "Myself2 Me1 I4 and3"

› Output: "Me Myself and I"

💡 Note: Rearrange by positions: Me1, Myself2, and3, I4 becomes "Me Myself and I"

Example 3 — Single Word

$ Input: s = "T4est1"

› Output: "T4est"

💡 Note: Single word with position 1, just remove the digit to get "T4est"

Constraints

s contains only lowercase and uppercase English letters, spaces and digits from 1 to 9
All the words in s are separated by a single space
s contains between 1 and 9 words, inclusive
Each word in s consists of lowercase and uppercase English letters
All the words have a unique position digit

Visualization

Tap to expand

Understanding the Visualization

Input

Shuffled sentence with position digits: "is2 sentence4 This1"

Process

Extract position from each word and place in correct order

Output

Reconstructed original sentence: "This is sentence"

Key Takeaway

🎯 Key Insight: Each word encodes its correct position as the last character - extract and place directly!

Asked in

a Amazon 15 M Microsoft 12

The key insight is that each word contains its correct position as the last character. We can extract this digit, remove it from the word, and place the cleaned word at the correct position in a result array. The optimal Array Placement approach runs in O(n) time and O(n) space by directly placing words at their target positions.

Common Approaches

Approach	Time	Space	Notes
✓ Sort by Position	O(n log n)	O(n)	Extract word-position pairs and sort them by position
Brute Force Array Placement	O(n)	O(n)	Extract each word's position and place it directly in result array

Sort by Position — Algorithm Steps

Step 1: Split sentence and extract (word, position) pairs
Step 2: Sort pairs by their position values
Step 3: Extract words from sorted pairs
Step 4: Join words into final sentence

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Pairs

Create (word, position) pairs from input

Sort Pairs

Sort pairs by position values

Extract Words

Take words from sorted pairs to form result

Code -

solution.c — C

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

typedef struct {
    char word[50];
    int position;
} WordPair;

int compare(const void* a, const void* b) {
    WordPair* pairA = (WordPair*)a;
    WordPair* pairB = (WordPair*)b;
    return pairA->position - pairB->position;
}

char* solution(char* s) {
    WordPair pairs[9];
    int wordCount = 0;
    
    char* token = strtok(s, " ");
    while (token != NULL && wordCount < 9) {
        int len = strlen(token);
        int position = token[len-1] - '0';
        token[len-1] = '\0';
        strcpy(pairs[wordCount].word, token);
        pairs[wordCount].position = position;
        wordCount++;
        token = strtok(NULL, " ");
    }
    
    qsort(pairs, wordCount, sizeof(WordPair), compare);
    
    char* result = malloc(1000);
    strcpy(result, pairs[0].word);
    for (int i = 1; i < wordCount; i++) {
        strcat(result, " ");
        strcat(result, pairs[i].word);
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting n words by their positions takes O(n log n) time

⚡ Linearithmic

Space Complexity

O(n)

Storage for word-position pairs and result array

⚡ Linearithmic Space

33.9K Views

Medium Frequency

~8 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

Sort by Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler