Skip to main content
Talentd

Sorting the Sentence - Solution & Explanation

EasyStringSorting11 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"
Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.

Example 2:

Input: s = "Myself2 Me1 I4 and3"
Output: "Me Myself and I"
Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.

 

Constraints:

  • 2 <= s.length <= 200
  • s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
  • The number of words in s is between 1 and 9.
  • The words in s are separated by a single space.
  • s contains no leading or trailing spaces.

Approach Overview

Problem Overview: You receive a shuffled sentence where each word ends with a digit representing its correct position in the sentence. Your task is to reorder the words based on these indices and return the original sentence without the digits.

The input looks like "is2 sentence4 This1 a3". Each word contains its position at the end. The goal is to place every word in its correct position and remove the trailing number.

Approach 1: Sorting + String Manipulation (O(n log n) time, O(n) space)

Split the sentence into words using whitespace. Each word contains its index as the last character, so you can extract that digit and use it as the sorting key. After sorting the array of words by their index, remove the trailing digit from each word and join them back into a sentence. This approach relies on built‑in sorting from the sorting category and basic string operations. The implementation is straightforward and readable, but the sort operation introduces O(n log n) time complexity.

Approach 2: Array Indexing (O(n) time, O(n) space)

The index digit at the end of each word already tells you the exact final position. Instead of sorting, create an array of size n where n is the number of words. Iterate through each word, extract the index, remove the digit, and place the word directly at result[index - 1]. After processing all words, join the array into the final sentence. This method avoids sorting completely and processes each word exactly once, achieving O(n) time. The approach uses simple array placement and string slicing.

The key insight is that the index digit encodes the final position explicitly. Sorting works because the digit defines order, but direct indexing is faster because it skips the comparison step entirely.

Recommended for interviews: Interviewers typically expect the linear-time array indexing solution. It demonstrates that you noticed the positional information embedded in each word and used it to avoid sorting. Showing the sorting approach first proves you understand the problem quickly, but implementing the O(n) direct placement solution shows stronger algorithmic thinking.

Approach 1: Using Sorting and String Manipulation

This approach involves splitting the input sentence into words, then individually processing each word to extract the index number, and finally sorting them based on these indices.

Once sorted, the index numbers can be removed, and the words rejoined to form the original sentence.

This Python solution first splits the input sentence into a list of words. It then sorts these words using a custom key function that extracts the last character (the positional index) from each word. Finally, it constructs the original sentence by removing these index numbers and joining the words.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(n log n), where n is the number of words, due to the sort operation.
Space Complexity: O(n), for storing the split words.

Try this approach in the editor →

Approach 2: Using Array Indexing

This method uses an array to directly place each word into its correct position using the appended index number. Once positioned correctly, the numbers are removed to form the original sentence.

The C++ solution processes each word to determine its position directly using the appended index. It places them into a predefined vector and constructs the output sentence by ignoring empty slots and joining the words.

Code

C++CC#

C++

C

C#

Complexity

Time Complexity: O(n), where n is the number of characters in the sentence.
Space Complexity: O(1), apart from the output string which is fixed sized due to constraint.

Try this approach in the editor →

Approach 3: String Splitting

First, we split the string s by spaces to get the array of strings ws. Then, we iterate through the array ws, subtracting the character '1' from the last character of each word to get the result as the index of the word. We take the prefix of the word as the content of the word. Finally, we concatenate the words in index order.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Sorting and String Manipulation

Time Complexity: O(n log n), where n is the number of words, due to the sort operation.
Space Complexity: O(n), for storing the split words.

Using Array Indexing

Time Complexity: O(n), where n is the number of characters in the sentence.
Space Complexity: O(1), apart from the output string which is fixed sized due to constraint.

String Splitting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + String ManipulationO(n log n)O(n)Quick and readable solution using built-in sorting
Array Indexing (Direct Placement)O(n)O(n)Optimal approach when positions are encoded in the data

Video Solution

Leetcode 1859. Sorting the Sentence || Biweekly Contest 52 problem 1 || Code + Explanation + Example • Code with Alisha • 14,151 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sorting the Sentence easy or hard?
Sorting the Sentence is classified as an Easy problem on LeetCode with a high acceptance rate above 80%. The challenge mainly involves recognizing that the trailing digit encodes the correct position of each word.
Sorting the Sentence Python/Java solution
In Python or Java, split the sentence into words, extract the final digit from each word, and either sort the words by that digit or place them directly in an array using the digit as the index. The array indexing approach runs in O(n) time.
How to solve Sorting the Sentence in O(n)?
Split the sentence into words and create a result array of size n. For each word, read the last character to determine its position, remove the digit, and store the word at result[index - 1]. Finally, join the array with spaces to form the reconstructed sentence.
What is the best approach for Sorting the Sentence?
The most efficient approach uses array indexing. Each word ends with a digit representing its final position, so you can place the word directly into a result array at index (digit - 1). This avoids sorting and runs in O(n) time with O(n) space.
Is Sorting the Sentence asked at Google/Amazon/Meta?
Sorting the Sentence is categorized as an easy string manipulation problem and is commonly used in interview preparation sets. Similar problems involving string parsing, indexing, and reconstruction appear in coding interviews at companies like Amazon and Google.
What data structure is used in Sorting the Sentence?
The optimal solution uses an array to store words at their correct positions. The problem also relies on string operations to extract the trailing index and remove it from the word.
What is the time complexity of Sorting the Sentence?
The optimal solution runs in O(n) time because each word is processed once and placed directly in its correct position. A simpler solution that sorts the words by their trailing digit runs in O(n log n) time due to the sorting step.

Ready to solve this problem?

Practice Sorting the Sentence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if Numbers Are Ascending in a Sentence