Skip to content
← All posts

Sorting the Sentence

4 min read
leetcodeproblemeasystringssorting

LeetCode 1859, Sorting the Sentence, gives you a shuffled sentence where each word has its original position number appended to the end. Your job is to reconstruct the original sentence.

For example:

  • "is2 sentence4 This1 a3" returns "This is a sentence"
  • "Myself2 Me1 I4 and3" returns "Me Myself and I"

Every word has exactly one digit (1 through 9) glued onto its tail. That digit tells you where the word belongs.

shuffled:is2sentence4This1a3result:Thispos 1ispos 2apos 3sentencepos 4
Each word carries its position number as a suffix. Extract the digit, strip it off, and place the word at the correct index.

The approach: split, extract, place, join

The trailing digit on each word is a built-in index. All you need to do is peel it off and use it.

Here is the plan:

  1. Split the input string by spaces to get an array of tagged words.
  2. Extract the last character of each word. That character is the position number. Everything before it is the actual word.
  3. Place each word into the correct slot in a result array, using the position number as the index (adjusting from 1-indexed to 0-indexed).
  4. Join the result array with spaces to produce the final sentence.

Because the positions are guaranteed to be 1 through n with no gaps, you never have to worry about collisions or missing slots. One pass through the words is all it takes.

The position is always a single digit (the problem guarantees at most 9 words). That means you can grab it with word[-1] in Python without parsing multi-digit numbers.

The code

def sortSentence(s: str) -> str:
    words = s.split()
    result = [""] * len(words)
    for word in words:
        idx = int(word[-1]) - 1
        result[idx] = word[:-1]
    return " ".join(result)

Walk through what happens:

  1. s.split() breaks the input on whitespace, giving you tokens like "is2", "sentence4", etc.
  2. For each token, word[-1] grabs the trailing digit and int(...) converts it to an integer. Subtracting 1 converts from 1-indexed to 0-indexed.
  3. word[:-1] slices off the last character, leaving the clean word. That word goes into result at the correct position.
  4. " ".join(result) glues everything back together.
Practice string manipulation problems

Visual walkthrough

Here is the algorithm running on "is2 sentence4 This1 a3".

Step 1: Split the string by spaces

"is2 sentence4 This1 a3"split(" ")is2sentence4This1a3

Splitting "is2 sentence4 This1 a3" gives four tokens.

Step 2: Extract the trailing number from each word

tokenwordpositionis2is2sentence4sentence4This1This1a3a3

The last character of each token is its position (1-indexed). The rest is the actual word.

Step 3: Place each word at its position

[0]This[1]is[2]a[3]sentence

Create an array of the right size, then slot each word in using its position number.

Step 4: Join with spaces

"This is a sentence"

Concatenate the sorted array into "This is a sentence".

After placing all four words, the result array reads ["This", "is", "a", "sentence"]. Joining with spaces gives the final answer.

Complexity analysis

MetricValue
TimeO(n), where n is the length of the input string
SpaceO(n), for the result array and the split tokens

Splitting the string is O(n). Iterating through the words and slicing each one is also O(n) total (each character is visited a constant number of times). Joining at the end is O(n). Everything is linear.

Drill string problems with spaced repetition

Building blocks

This problem uses two techniques that appear across many string and array problems.

String slicing with index extraction

The idea of pulling a meaningful value out of a specific position in a string (here, the last character) comes up constantly. You will see it in problems that encode metadata inside strings, like parsing log entries, version numbers, or tagged tokens. The key skill is knowing how to slice precisely: word[:-1] for the body, word[-1] for the tag.

Direct-address placement

Instead of sorting with a comparison function, you use the position number to place each element directly into the right slot. This is the same idea behind counting sort and bucket sort. When you already know where each element belongs, there is no need to compare elements against each other.

Edge cases

Single word. The input "Hello1" has just one word. The loop runs once, places "Hello" at index 0, and the result is "Hello".

Already sorted. The input "A1 B2 C3" is already in order. The algorithm does not care. It extracts positions and places words the same way regardless.

Words of varying length. Short words like "a3" and long words like "sentence4" are handled identically. The trailing digit is always the last character, and word[:-1] always gives the rest.

Maximum size. With at most 9 words and each word up to 200 characters, the input never exceeds 1809 characters. Performance is never a concern here, but the linear approach scales cleanly.

From understanding to recall

You can read through this solution and feel like you have it down. But when a similar string-parsing problem appears in an interview two weeks from now, will you instinctively reach for the "extract trailing metadata and direct-place" pattern?

Spaced repetition helps you lock in the building blocks. Instead of re-reading the full solution, you drill the individual pieces (split on whitespace, slice the last character, convert to index, place directly) at increasing intervals. After a few reps spread over days, the pattern becomes automatic. When you see a shuffled-data problem, the approach is already in your toolkit.

Try CodeBricks free

Related posts