LeetCode 1859 - Sorting the Sentence

The problem gives us a shuffled sentence, where every word has a number appended to its end. That number represents the word's original position in the sentence, using 1-indexed ordering.

leetcodeeasystringsorting

LeetCode Problem 1859

Difficulty: šŸŸ¢ Easy
Topics: String, Sorting

Solution

Problem Understanding

The problem gives us a shuffled sentence, where every word has a number appended to its end. That number represents the word's original position in the sentence, using 1-indexed ordering.

For example, the word "This1" means "This" originally appeared in position 1, while "sentence4" means "sentence" originally appeared in position 4.

The words in the sentence have then been rearranged arbitrarily. Our task is to reconstruct the original sentence by:

  1. Determining the correct order of words using the trailing digit.
  2. Removing the digit from each word.
  3. Joining the words back together with spaces.

The input is a string s containing words separated by single spaces. Each word consists of English letters followed by a digit between 1 and 9.

The expected output is a reconstructed sentence string where:

  • Words appear in their original order.
  • The appended position numbers are removed.
  • Words are separated by a single space.

The constraints are small:

  • s.length <= 200
  • At most 9 words exist in the sentence.
  • Word positions are always between 1 and 9.

These constraints tell us the problem size is extremely small. Even less efficient solutions would perform fine. However, the goal is to write a clean and logically sound solution.

An important guarantee is that every word has a valid trailing digit representing its unique position. Since positions are guaranteed to exist and be valid, we do not need to handle malformed input.

Some edge cases that could trip up a naive implementation include:

  • A sentence containing only one word, where reconstruction is trivial.
  • Words appearing in completely random order, requiring full reordering.
  • Multi-character words with mixed uppercase and lowercase letters, meaning we cannot assume only lowercase input.
  • Ensuring we correctly separate the last character digit from the actual word content.

Approaches

Brute Force Approach

A straightforward brute-force approach would repeatedly search for the word corresponding to position 1, then position 2, and so on.

We could split the sentence into words, then for every expected position from 1 to n, scan all words to find the one whose last character matches that position. Once found, remove the digit and append the cleaned word to the result.

This works because every word contains its exact original index, guaranteeing we can reconstruct the sentence correctly.

However, this approach is inefficient because for each position, we scan through the entire list of words again. If there are n words, this results in O(nĀ²) time complexity.

Given that n <= 9, this inefficiency is not practically harmful, but we can do better.

Optimal Approach

The key observation is that the final digit directly tells us where a word belongs.

Instead of repeatedly searching, we can:

  1. Split the sentence into words.
  2. Create an array of size n.
  3. For each word:
  • Read the last character to get its position.
  • Remove the trailing digit.
  • Place the cleaned word directly into the correct index.
  1. Join the array into the final sentence.

This works efficiently because each word is processed exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(n) Repeatedly scans all words for each position
Optimal O(n) O(n) Places each word directly into its correct position

Algorithm Walkthrough

  1. Split the input sentence into a list of words using spaces.

We do this because each word contains both its content and ordering digit. Processing words individually makes extraction easier. 2. Create a result array with the same number of elements as the number of words.

Since positions are 1-indexed, we need a place to store words directly in their correct order. An array allows constant-time placement. 3. Iterate through every word.

For each word:

  • Read the last character to determine the word's position.
  • Convert the digit into an integer.
  • Subtract 1 because Python and Go arrays are 0-indexed.
  • Remove the final character from the word to get the actual text.
  • Store the cleaned word in the appropriate position in the result array.
  1. Join the ordered words with spaces.

Once every word is placed correctly, combine them into a single sentence using " ".join(...) in Python or strings.Join(...) in Go.

Why it works

The correctness of this algorithm comes from the guarantee that each word contains its exact original position as a unique trailing digit. Since every word is placed directly into its indexed position exactly once, the reconstructed array necessarily represents the original sentence order. Removing the digit afterward restores the original word text.

Python Solution

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split()
        ordered_words = [""] * len(words)

        for word in words:
            position = int(word[-1]) - 1
            ordered_words[position] = word[:-1]

        return " ".join(ordered_words)

The implementation begins by splitting the sentence into individual words. Since each word includes its original position at the end, we create a result array called ordered_words to store words in their correct order.

We then iterate through every word. The last character, word[-1], contains the position digit. After converting it to an integer and subtracting 1, we obtain the correct zero-based index.

The actual word text is extracted using word[:-1], which removes the trailing digit. We place this cleaned word into the correct location in the result array.

Finally, we join all ordered words with spaces to reconstruct the original sentence.

Go Solution

package main

import (
	"strconv"
	"strings"
)

func sortSentence(s string) string {
	words := strings.Split(s, " ")
	orderedWords := make([]string, len(words))

	for _, word := range words {
		position, _ := strconv.Atoi(string(word[len(word)-1]))
		orderedWords[position-1] = word[:len(word)-1]
	}

	return strings.Join(orderedWords, " ")
}

The Go implementation follows the same logic as the Python version. Since Go strings are immutable, we use slicing to remove the last character.

One Go-specific difference is converting the last character into an integer. We first convert the character into a string and then use strconv.Atoi().

Error handling from strconv.Atoi() is ignored safely here because the problem guarantees valid input, meaning every word always ends with a digit from 1 to 9.

Worked Examples

Example 1

Input:

"is2 sentence4 This1 a3"

After splitting:

["is2", "sentence4", "This1", "a3"]

We initialize:

ordered_words = ["", "", "", ""]
Current Word Position Cleaned Word Result Array
"is2" 2 ā†’ index 1 "is" ["", "is", "", ""]
"sentence4" 4 ā†’ index 3 "sentence" ["", "is", "", "sentence"]
"This1" 1 ā†’ index 0 "This" ["This", "is", "", "sentence"]
"a3" 3 ā†’ index 2 "a" ["This", "is", "a", "sentence"]

Final join:

"This is a sentence"

Example 2

Input:

"Myself2 Me1 I4 and3"

After splitting:

["Myself2", "Me1", "I4", "and3"]

Initial array:

["", "", "", ""]
Current Word Position Cleaned Word Result Array
"Myself2" 2 ā†’ index 1 "Myself" ["", "Myself", "", ""]
"Me1" 1 ā†’ index 0 "Me" ["Me", "Myself", "", ""]
"I4" 4 ā†’ index 3 "I" ["Me", "Myself", "", "I"]
"and3" 3 ā†’ index 2 "and" ["Me", "Myself", "and", "I"]

Final result:

"Me Myself and I"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each word is processed exactly once
Space O(n) We store the reordered sentence in an additional array

The algorithm visits every word exactly one time, and each operation inside the loop is constant time. Therefore, the total runtime is linear in the number of words.

The extra space comes from the ordered_words array, which stores the reconstructed sentence before joining.

Test Cases

solution = Solution()

# Provided examples
assert solution.sortSentence("is2 sentence4 This1 a3") == "This is a sentence"  # Example 1
assert solution.sortSentence("Myself2 Me1 I4 and3") == "Me Myself and I"  # Example 2

# Minimum valid case
assert solution.sortSentence("hello1") == "hello"  # Single word sentence

# Already sorted sentence
assert solution.sortSentence("This1 is2 fine3") == "This is fine"  # No rearrangement needed

# Reverse order
assert solution.sortSentence("world2 Hello1") == "Hello world"  # Completely reversed

# Mixed capitalization
assert solution.sortSentence("World2 Hello1") == "Hello World"  # Preserve case sensitivity

# Maximum word positions
assert solution.sortSentence(
    "nine9 eight8 seven7 six6 five5 four4 three3 two2 one1"
) == "one two three four five six seven eight nine"  # Largest valid ordering

# Random ordering
assert solution.sortSentence("code3 love2 I1") == "I love code"  # Arbitrary shuffle
Test Why
"is2 sentence4 This1 a3" Validates provided example
"Myself2 Me1 I4 and3" Verifies second provided example
"hello1" Tests smallest possible sentence
"This1 is2 fine3" Ensures already sorted input works
"world2 Hello1" Validates reversed ordering
"World2 Hello1" Confirms capitalization is preserved
Maximum 9-word example Tests upper bound on word positions
"code3 love2 I1" Verifies arbitrary shuffling

Edge Cases

Single Word Sentence

A sentence containing only one word, such as "hello1", could expose indexing mistakes or assumptions that multiple words always exist. The implementation handles this naturally because the result array has size 1, and the only word is placed at index 0.

Already Sorted Input

The shuffled sentence may already appear in correct order, such as "This1 is2 fine3". A poorly designed solution might unnecessarily rearrange or corrupt ordering. Since our implementation places words strictly according to their position digit, the correct order is preserved automatically.

Maximum Position Value

The problem allows positions from 1 to 9. Inputs such as "nine9 eight8 ... one1" verify that indexing logic works for the highest allowed digit. By subtracting 1 from the digit, the implementation correctly maps 9 to array index 8.

Mixed Capitalization

Words may contain both uppercase and lowercase letters. A bug-prone implementation might unintentionally normalize casing or manipulate characters incorrectly. Since we only remove the final digit and never modify the remaining text, capitalization remains unchanged.