Rearrange words in a sentence

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
Goldman SachsBarclays

Problem statement

You are given a sentence 'TEXT'. Each word of 'TEXT' is separated by a single space and the first letter of 'TEXT' is capital. You need to rearrange the words of Text in increasing order of their length.

Note: 
If two words have the same length then the word which comes first in 'TEXT' also comes first in the rearranged sentence.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains a single sentence 'TEXT'.
Output Format: 
For each test case, return the rearranged sentence.
Constraints: 
1 <= T <= 5
1 <= | TEXT | <= 10^5

Where | 'TEXT' | denotes the length of the 'TEXT' sentence.

Time limit: 1 sec
Sample Input 1:
2
Do you have a knack for coding
Hello ninjas
Sample Output 1:
A do you for have knack coding
Hello ninjas
Explanation For Sample Output 1:
In test case 1: Output is ordered as follows:

“A” has 1 character
“do” has 2 characters
“you”, “for” both have 3 characters, so arranging them in order of their positions in the original Text.
“have” has 4 character
“knack” has 5 characters
“coding” has 6 characters

In test case 2, Output is ordered as follows:

“hello” has 5 characters
“ninjas” has 6 characters
Sample Input 2:
2
Take it 
Cool
Sample Output 2:
It take 
Cool
Explanation For Sample Output 2:
In test case 1: Output is ordered as follows:

“It” has 2 characters
“take” has 4 characters.

In test case 2, Output is ordered as follows:

“Cool” has 4 characters.
Hint

Sort the words in increasing order of length.

Approaches (1)
Using Sorting

The idea is to create an array of pairs, ‘WORD’, of size ‘N’. Where the first element of pair is word length and the second element is the starting index of word.

 

Now, start iterating over ‘TEXT’ starting from index 0 and maintain a variable ‘currentStart’ to store the starting index of the current word. Whenever you encounter space(“ “) say at index ‘C’, it means your current word starting from index ‘currentStart’ ends at index ‘C’ - 1 and its length is c - ‘currentStart’. Insert the pair { ‘C’ - ‘currentStart’, ‘currentStart' } in your 'WORD' array and update 'currentStart' with ‘C’ + 1 ( the starting index of next word). Repeat steps till the string ends.

 

Now, sort the 'WORD' array in increasing order of word length, if word length is the same for two words then sort them in increasing order of their starting index.

 

  • For example: Consider the Text is “Coding is fun”.
  • Now the Word array for this Text is = [{6,0}, {2,7}, {3,10}]. After sorting it becomes [{2,7}, {3,10}, {6,0}].

 

Now iterate over the 'WORD' array and for each ‘WORD[i]’ with value {a ,b}, start inserting characters of original text starting from index b and till index a + b - 1 ( as word length is a ) in your answer sentence say 'ANS'.

 

Make the first character of 'ANS' capital and return ‘ANS’.

Time Complexity

O( N * logN ), Where ‘N’ is the length of Text.

 

Since we are traversing the input text once which takes O(N) time and we are sorting the Word array of size L which takes O(L * log(L)) time where L is the number of words in Text.In the worst case, number of words can be N / 2 so sorting Word array takes O(N * logN). Thus the final time complexity is O(N) + O(N * log(N)) = O(N * log(N)).

Space Complexity

O(N), Where ‘N’ is the length of Text.

 

Since we are creating a Word array of size N / 2 (when the length of each word is 1). Thus the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Rearrange words in a sentence
Full screen
Console