Last Updated: 13 Oct, 2021

All Sentences with Same Order

Moderate

Asked in company

Solve now

Problem statement

You are given ‘N’ characters, these characters can be used to construct words and these words can further be used to construct sentences.

Find all the distinct sentences that you can build while maintaining the relative order of these characters. Print the sentences in lexicographical order.

For Example :

If N = 3 and characters are = { a, b, c }
Then the four distinct sentences you can build:
a b c 
a bc 
ab c 
abc

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the number of characters.

The second line of each test case consists of a string ‘S’ denoting the characters.

Output Format :

For each test case, print all the sentences that can be built in separate lines.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10      
1 ≤ N ≤ 15

String ‘S’ consist of only lower case English alphabets

Time limit: 1 sec

Solve now

Approaches

01 Approach

If you have previously solved the problem of generating all subsets then you will probably find this problem very familiar.

You need to insert spaces between the characters to generate all possible sentences. Note that there are N-1 places and each place has two options, it will either have a space or not, this will finally lead to the generation of 2^N-1 sentences. Also notice that even if you have duplicate characters still you won’t generate duplicate sentences, and the answer will still consist of 2^N-1 sentences.

To generate all the sequences, you can easily backtrack to find all the sequences of size equal to N-1 and consisting of 0 and 1, where 1 denotes that the i^th place has space between characters. You can store all the there strings in an array of array-of-strings and finally, sort it and return it.

The steps are as follows :

Initialize ‘ans’ array of array-of-strings of size equal to 2^N-1to store the final answer.
Initialize ‘temp’ array to store the current generated sequence of 0’s and 1’s.
Check for the border case of ‘N’ equals 1, for this case simply insert the single character in ‘ans’ and return it.
Make an initial call to the backtracking function.
In the backtracking function, use standard backtracking to find all the sequences of 0’s and 1’s of length equal to N-1, and for each generated sequence fill one of the positions in ‘ans’ corresponding to the logic discussed above, the current sentence will be stored as an array of strings(words) and we will need to generate the words one by one corresponding to placing spaces between characters, refer the code for better understanding.
Finally, sort ‘ans’ and return it.

Solve now