Last Updated: 24 Dec, 2020
Subsequences of String
Moderate
Asked in companies
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.
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
Approaches
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 :
- Find the length, N, of the input string.
- 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.
- Save all the subsequences in a list and return that list.
For every character of the input string there are two options, one is to include it in the current subsequence and another is not including it in the current subsequence. This will lead to all possible subsequences of the input string. This can be done using recursion.
Algorithm:
- Take an empty set and an empty list to store all the subsequences.
- Base Case: If there are no more characters in the string to include in the current subsequence, that means that the current subsequence is done.
- Check if the current subsequence already exists in our answer, otherwise append it in the final answer.
- If there are still letters left to process in the input string:
- Iterate over the letters and once append the current letter in the current subsequence and proceed further.
- And once don’t include the current letter in the current subsequence and proceed further.