Last Updated: 10 Mar, 2021
Ninja and Strings
Moderate
Asked in companies
Ninja has been given a string ‘STR’ containing lowercase english alphabets. He wants to generate all the possible subsequences of the ‘STR’ in lexicographically sorted order.
For example: For ‘STR’ = “abc” following are the subsequences in lexicographically sorted order:
[“a”], [“ab”], [“abc”], [“ac”], [“b”], [“bc”], [“c”]
Ninja is busy with some other task so he asks you for help.
Can you help Ninja to generate all the possible subsequences of the given string ‘STR’ in lexicographically sorted order?
Input Format:
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and the only line of each test case contains a string ‘STR’.
Output Format :
For each test case, print all the possible subsequences of the given string ‘STR’ in lexicographically sorted order.
Print the output of each test case in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
1 <= |STR| <= 10
Where |STR| represents the length of ‘STR’.
Time Limit: 1 sec
Approaches
Approach: The basic idea is to generate all the subsequences of the ‘STR’ and store all the strings in the array/list. Then we can simply sort the array/list to get all subsequences in lexicographically increasing order.
To generate all the subsequences, we will use bit patterns from binary representation of 1 to (2 ^ ‘|STR|’) – 1. here ‘|STR|’ represents the length of ‘STR’.
For example: For ‘STR’ = “abc”
- We will consider the binary representation 1 to (2 ^ 3 - 1), i.e from 1 to 7.
- Start from left i.e most significant bit (MSB) to right i.e the least significant bit(LSB) of binary representation.
Append characters from the input string that corresponds to the bit value 1 in binary representation to the string subsequence.
- 001 => “abc” . Only c corresponds to bit 1. So, the subsequence is “c”.
- 101 => “abc” . “a” and “c” corresponds to bit 1. So, the subsequence is “ac”.
Here is the complete algorithm:
- Store 2 ^ ‘|STR|’ in a variable ‘SIZE’.
- Make an array/list ‘TEMP’ of type string to store the subsequences.
- Run a for loop from ‘i’ = 1 to ‘i’ < ‘SIZE’ and for each ‘i’ do the following:
- Declare an empty string ‘S’.
- Run a for loop from ‘j’ = 0 to ‘j’ < |STR| and for each ‘j’ do the following:
- If ( ‘i’ & ( 1 << ‘j’ ) ) is not zero then push ‘STR[j]’ in ‘S’.
- Insert ‘S’ into the ‘TEMP’.
- Finally, sort the ‘TEMP’ and return ‘TEMP’.
Similar problems