Sorting the Sentence

Easy

#1698Time: 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.

Algorithms

Sorting

Data structures

String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public String sortSentence(String s) {3        String[] words = s.split(" ");4        5        Arrays.sort(words, (a, b) -> a.charAt(a.length() - 1) - b.charAt(b.length() - 1));6        7        StringBuilder result = new StringBuilder();8        for (String word : words) {9            result.append(word.substring(0, word.length() - 1));10            result.append(" ");11        }12        13        return result.toString().trim();14    }15}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public String sortSentence(String s) {3        String[] shuffledWords = s.split(" ");4        String[] resultArray = new String[shuffledWords.length];5        6        for (String word : shuffledWords) {7            int index = word.charAt(word.length() - 1) - '1'; // '1' -> 0, '2' -> 1, etc.8            String actualWord = word.substring(0, word.length() - 1);9            resultArray[index] = actualWord;10        }11        12        return String.join(" ", resultArray);13    }14}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ); } }

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

1class 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 ; } };

1class 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 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem