# Sorting the Sentence
**Difficulty:** EASY
[External](https://leetcode.com/problems/sorting-the-sentence)
Canonical: https://scaleengineer.com/dsa/problems/sorting-the-sentence
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** String
---
## Problem
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.

# Approaches
## Sorting with a Custom Comparator
This approach involves splitting the input sentence into individual words. Then, we sort these words based on the numeric index appended to each word. After sorting, the words are in their correct order. Finally, we remove the numeric indices and join the words back into a single sentence.
**Time:** O(L + N log N), where L is the length of the string and N is the number of words. Splitting the string takes O(L). Sorting N words takes O(N log N) comparisons. Building the final string takes O(L). The overall complexity is dominated by these steps. · **Space:** O(L), where L is the length of the input string. This space is required to store the array of words after splitting the input string.
**Pros:** Conceptually simple as it leverages built-in sorting functionalities.; The implementation is straightforward and easy to understand.
**Cons:** Less efficient than a direct placement approach due to the O(N log N) sorting overhead, which is not optimal when direct indices are available.
### Explanation
The core idea of this method is to leverage a standard sorting algorithm.

First, the input string `s` is split by spaces to get an array of shuffled words (e.g., `["is2", "sentence4", "This1", "a3"]`). We then use a sorting function, like `Arrays.sort` in Java, with a custom comparator. The comparator function takes two words (e.g., `"is2"` and `"This1"`) and compares them based on their last character, which represents the original position. Since '1' comes before '2', `"This1"` is placed before `"is2"`. After sorting, the array becomes `["This1", "is2", "a3", "sentence4"]`.

A `StringBuilder` is then used to efficiently construct the final sentence. We iterate through the sorted array, and for each word, we append the word (without its last character) followed by a space to the `StringBuilder`. Finally, we convert the `StringBuilder` to a string and trim any trailing space to get the desired output.

```java
class Solution {
    public String sortSentence(String s) {
        String[] words = s.split(" ");
        
        Arrays.sort(words, (a, b) -> a.charAt(a.length() - 1) - b.charAt(b.length() - 1));
        
        StringBuilder result = new StringBuilder();
        for (String word : words) {
            result.append(word.substring(0, word.length() - 1));
            result.append(" ");
        }
        
        return result.toString().trim();
    }
}
```
### Algorithm
*   Split the input string `s` by spaces into an array of strings `words`.
*   Sort the `words` array using a custom comparator.
*   The comparator logic should compare two words based on the integer value of their last character.
*   Initialize an empty `StringBuilder` called `result`.
*   Iterate through the sorted `words` array.
*   For each `word`, extract the substring without the last character and append it to `result`, followed by a space.
*   Convert `result` to a string and remove the trailing space.
*   Return the final string.

## Direct Placement using an Auxiliary Array
This approach is more efficient as it avoids a full sorting operation. We split the sentence into words, then use an auxiliary array to place each word directly into its correct final position. The position is determined by the number at the end of each shuffled word. After all words are placed, we join them to form the sentence.
**Time:** O(L), where L is the length of the input string. Splitting the string, iterating through the words to place them in the result array, and joining the final string are all operations that take time proportional to the total length of the string. · **Space:** O(L), where L is the length of the input string. We need space for the `shuffledWords` array and the `resultArray`, both of which together store all the characters of the original string.
**Pros:** Highly efficient with a linear time complexity O(L).; It is the optimal approach as it directly maps words to their positions without the need for comparison-based sorting.
**Cons:** Requires extra space for the auxiliary array, although this is comparable to the space used by the sorting approach.
### Explanation
This method takes advantage of the fact that the appended number directly tells us the final position of the word, which allows for a linear time solution similar to a bucket sort.

First, we split the input string `s` into an array of shuffled words. We then create a new string array, `resultArray`, with a size equal to the number of words. This array will hold the words in their correct order.

We iterate through each `word` in the shuffled array. For each `word`, we extract its intended position from the last character. For example, for `"This1"`, the last character is '1'. We convert this to a 0-based index by calculating `'1' - '1' = 0`. We then extract the actual word by taking the substring of the `word` excluding the last character (e.g., `"This"`). This extracted word is placed into `resultArray` at the calculated index.

After processing all words, `resultArray` will contain the words in their correct, sorted order. Finally, we use `String.join(" ", resultArray)` to combine the words into the final sentence.

```java
class Solution {
    public String sortSentence(String s) {
        String[] shuffledWords = s.split(" ");
        String[] resultArray = new String[shuffledWords.length];
        
        for (String word : shuffledWords) {
            int index = word.charAt(word.length() - 1) - '1'; // '1' -> 0, '2' -> 1, etc.
            String actualWord = word.substring(0, word.length() - 1);
            resultArray[index] = actualWord;
        }
        
        return String.join(" ", resultArray);
    }
}
```
### Algorithm
*   Split the input string `s` by spaces into an array `shuffledWords`.
*   Create a new string array `resultArray` of the same size as `shuffledWords`.
*   Iterate over each `word` in `shuffledWords`.
*   Get the last character of the `word` and convert it to a 0-based index (e.g., '1' becomes 0, '2' becomes 1).
*   Extract the actual word by taking the substring without the last character.
*   Store this actual word at the calculated index in `resultArray`.
*   After the loop finishes, join the elements of `resultArray` with a single space in between to form the final sentence.
*   Return the resulting string.

# Solutions
### Java

```java
class Solution { public String sortSentence ( String s ) { String [] ws = s . split ( " " ); int n = ws . length ; String [] ans = new String [ n ]; for ( int i = 0 ; i < n ; ++ i ) { String w = ws [ i ]; ans [ w . charAt ( w . length () - 1 ) - '1' ] = w . substring ( 0 , w . length () - 1 ); } return String . join ( " " , ans ); } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {string} */ var sortSentence = function (s) {
  const ws = s.split(" ");
  const ans = Array(ws.length);
  for (const w of ws) {
    ans[w.charCodeAt(w.length - 1) - " 1 ".charCodeAt(0)] = w.slice(0, -1);
  }
  return ans.join(" ");
};

```

### CPP

```cpp
class Solution { public: string sortSentence ( string s ) { istringstream iss ( s ); string w ; vector < string > ws ; while ( iss >> w ) { ws . push_back ( w ); } vector < string > ss ( ws . size ()); for ( auto & w : ws ) { ss [ w . back () - '1' ] = w . substr ( 0 , w . size () - 1 ); } string ans ; for ( auto & w : ss ) { ans += w + " " ; } ans . pop_back (); return ans ; } };
```

### Python

```python
class Solution : def sortSentence ( self , s : str ) -> str : ws = [( w [: - 1 ], int ( w [ - 1 ])) for w in s . split ()] ws . sort ( key = lambda x : x [ 1 ]) return ' ' . join ( w for w , _ in ws )
```