Problem of the day
You are given a string 'STR' containing lowercase English letters from a to z inclusive. Your task is to find all non-empty possible subsequences of 'STR'.
A Subsequence of a string is the one which is generated by deleting 0 or more letters from the string and keeping the rest of the letters in the same order.
The first line of input contains an integer ‘T’ denoting the number of test cases. Then T test cases follow.
The first and only line of each test case contains string 'STR'.
Output Format
For each test case, print the subsequences of the string 'STR' separated by space.
The output of each test case is printed in a separate line.
The output strings can be returned in any order.
Note
You don’t have to print anything, it has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= |STR| <= 16
Where |STR| represents the length of the string 'STR'.
Time Limit: 1 sec
1
abc
a ab abc ac b bc c
All possible subsequences of abc are :
“a” , “b” , “c” , “ab” , “bc” , “ac”, “abc”
1
bbb
b b b bb bb bb bbb
Use the concept of Power Set.
The idea is to use bit patterns from binary representation of 1 to 2^length - 1. For a string of length N, use the binary representation of all the numbers from 1 to (2^N - 1). Start from left (Most significant bit) to right (Least significant bit) and append characters from input string which corresponds to bit value 1 in binary representation to the current subsequence.
For example: “abc”
Binary representation from 1 to 2^3 - 1 that is 1 to 7
BinaryRepresentation for 1 is 001 which corresponds to substring “c”.
BinaryRepresentation for 2 is 010 which corresponds to substring “b”.
BinaryRepresentation for 3 is 011 which corresponds to substring “bc”.
BinaryRepresentation for 4 is 100 which corresponds to substring “a”.
BinaryRepresentation for 5 is 101 which corresponds to substring “ac”.
BinaryRepresentation for 6 is 110 which corresponds to substring “ab”.
BinaryRepresentation for 7 is 111 which corresponds to substring “abc”.
O(2^N * N), where N is the number of letters in the string S.
There will be 2^N bit representations with at max N set bits. Also, for each representation, we will take O(N) time to get the corresponding string. Thus, the final time complexity will be O(2^N * N).
O(N^2), where N is the number of letters in the string S.
Since, we are storing all the subsequences, which can be at max N*(N-1)/2 in number, thus the final space complexity is O(N^2).