All Sentences with Same Order

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
ShareChat

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
abc
2
xy
Sample Output 1 :
a b c 
a bc 
ab c 
abc 
x y 
xy
Explanation For Sample Input 1 :
For test case 1 :
There are four distinct sentences we can build from “abc” such that the order of characters doesn’t change, these sentences are:
a b c 
a bc 
ab c 
abc

For test case 2 : 
There are two distinct sentences we can build from “xy” such that the order of characters doesn’t change, these sentences are:
x y
xy

(Note that the result is printed in lexicographical order)
Sample Input 2 :
2
1
a
2
cd
Sample Output 2 :
a
c d
cd
Hint

You just have to manage a way to insert spaces between characters to generate all possible sentences.

Approaches (1)
Backtracking

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 2N-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 2N-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 ith 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 2N-1 to 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.
Time Complexity

O( N  *  2 ^ ( N - 1 ) ), where N denotes the number of characters

 

There are 2^(N - 1) sentences that be generated, and for each sentence, we iterate through all the N characters to generate all the sentences.

Hence the time complexity is O( N * 2 ^ (N - 1) ).

Space Complexity

O( N  *  2 ^ ( N - 1 ) ), where N denotes the number of characters

 

We require an auxiliary space of ~(N * 2^(N - 1)) to store all the ~2^(N-1) sentences each containing ~N letters.

Hence the space complexity is O( N * 2^(N-1) ).

Code Solution
(100% EXP penalty)
All Sentences with Same Order
Full screen
Console