Last Updated: 6 Jan, 2021

Rearrange words in a sentence

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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’.

Solve now