Sorting the Sentence

Easy
229.

Sorting the Sentence

Sorting the Sentence is an easy coding problem on strings and sorting, asked in Amazon and Zoho interviews.

A sentence was shuffled by appending the 1-indexed position of each word to the end of that word, then rearranging the words.

Given such a shuffled sentence s, reconstruct and return the original sentence.

Example 1

Input
s = "is2 sentence4 This1 a3"
Output
This is a sentence

Example 2

Input
s = "Myself2 Me1 I4 and3"
Output
Me Myself and I

Example 3

Input
s = "there1"
Output
there

Constraints

  • 2 <= s.length <= 60
  • Each word ends in a single digit giving its position.
  • There are at most 9 words.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var sortSentence = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sorting the Sentence — Solution in Python, Java & C++

Sorting the Sentence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Sorting the Sentence is an easy coding problem on strings and sorting, asked in Amazon and Zoho interviews.

  • Difficulty: Easy
  • Topics: Strings, Sorting
  • Asked at: Amazon, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A sentence was shuffled by appending the 1-indexed position of each word to the end of that word, then rearranging the words.

Given such a shuffled sentence s, reconstruct and return the original sentence.

Example 1

Input: s = "is2 sentence4 This1 a3"
Output: This is a sentence

Example 2

Input: s = "Myself2 Me1 I4 and3"
Output: Me Myself and I

Example 3

Input: s = "there1"
Output: there

Constraints

  • 2 <= s.length <= 60
  • Each word ends in a single digit giving its position.
  • There are at most 9 words.

Hints for Sorting the Sentence

  1. Hint 1

    The last character of each word is its destination, 1-indexed.

  2. Hint 2

    Strip that digit off and write the remaining word straight into its slot.

  3. Hint 3

    Then join the slots with single spaces.

How to solve Sorting the Sentence

Each word's last character is its 1-based destination; strip it and drop the word into that slot.

Approach

  1. Split on spaces.
  2. For each word, write word[:-1] into out[int(word[-1]) - 1].
  3. Join the slots with a space.

Why it works

The position suffix is a permutation of 1..n, so every slot is filled once and the join restores the original order.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • At most 9 words, so the suffix is a single digit — parsing word[-1] is enough.

Reference solution

Python

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

Java

public static String sortSentence(String s) {
    String[] pieces = s.split(" ");
    String[] out = new String[pieces.length];
    for (String w : pieces) {
        int pos = w.charAt(w.length() - 1) - '0';
        out[pos - 1] = w.substring(0, w.length() - 1);
    }
    return String.join(" ", out);
}

C++

string sortSentence(string s) {
    vector<string> pieces;
    string cur = "";
    for (char c : s) {
        if (c == ' ') { pieces.push_back(cur); cur = ""; }
        else cur += c;
    }
    pieces.push_back(cur);
    vector<string> out(pieces.size());
    for (string& w : pieces) {
        int pos = w[w.size() - 1] - '0';
        out[pos - 1] = w.substr(0, w.size() - 1);
    }
    string result = "";
    for (size_t i = 0; i < out.size(); i++) {
        if (i > 0) result += " ";
        result += out[i];
    }
    return result;
}

JavaScript

var sortSentence = function(s) {
    const parts = s.split(" ");
    const out = new Array(parts.length).fill("");
    for (let i = 0; i < parts.length; i++) {
        const w = parts[i];
        const pos = parseInt(w[w.length - 1], 10);
        out[pos - 1] = w.slice(0, w.length - 1);
    }
    return out.join(" ");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sorting Algorithms