Subsequences of String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
252 upvotes
Asked in companies
AmazonCiscoShareChat

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Input format:
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. 
Constraints:
1 <= T <= 10 
1 <=  |STR| <= 16

Where |STR| represents the length of the string 'STR'.

Time Limit: 1 sec
Sample Input 1:
1 
abc
Sample Output 1:
a ab abc ac b bc c
Explanation of sample input 1:
All possible subsequences of abc are :  
“a” , “b” , “c” , “ab” , “bc” , “ac”, “abc”
Sample Input 2:
1
bbb
Sample Output 2:
b b b bb bb bb bbb
Hint

Use the concept of Power Set.

Approaches (2)
Binary Representation approach

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

 

Algorithm : 

  1. Find the length, N, of the input string.
  2. For all the integers from 1 to 2^N - 1, find the corresponding string. To do that, find the rightmost set bit, add the character corresponding to this bit from the input string and then reset this bit. Repeat this process until all the bits are reset.
  3. Save all the subsequences in a list and return that list.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Subsequences of String
Full screen
Console