Subsequence of a String

Problem Statement

You are given a string as an input. The task is to print all the possible subsequence of a string in any order.

Example: str="abcd"

• "ad" is a subsequence of str obtained by deleting 'b' and 'c'.
• "ca" is not a subsequence of str because the order of elements is different from the input string.

Example

Let us understand the subsequence of string problem with the help of examples

Example1: str="abc"

Output:

Example2: str="dd"

Output:

Example Explanation

Example1: Subsequence are generated by deleting zero or more characters of the string without changing the order of the remaining elements. So first of all we will try to generate the subsequence by deleting zero characters. So when we delete zero characters then we get only one subsequence i.e "abc". Now we try to generate the subsequence after deleting one character from the string. So we get three subsequence after deleting one character i.e "ab","ac","bc". Now we try to generate the subsequence after deleting two characters from the string. So we get two subsequence after deleting two character i.e "a","b","c". And when we try to generate the subsequence by deleting three characters then we get an empty string. So we are not required to print that. So we can delete maximum length-1 characters.

Example2: First of all, we will try to generate the subsequence by deleting zero characters. So when we delete zero characters then we get only one subsequence i.e "dd". Now we try to generate the subsequence after deleting one character from the string. So we get two subsequence after deleting one character i.e "d","d". And when we try to generate the subsequence by deleting two characters then we get an empty string. So we are not required to print that.

Input

You are given a string str as an input.

Output

You need to display all the subsequences of the input string. There is no restriction on the order of the subsequences, you can display subsequences in any order.

Constraints

Algorithm 1 - Pick and Don’t Pick Concept

Approach

In the Pick and Don’t Pick Concept of this problem, we pick the first character of the input string and append it to the output and call the subsequence function and this continues until the string becomes empty and then again calls the subsequence function without appending the first character in the output. This will also require to do until the input string does not become empty.

Algorithm

1. Given an input string input_str and for output, we use output_str.
2. Now remove the first character of input_str.
3. Call the subsequence function recursively appending the first character of input_str in an output_str.
4. When the input_str become empty then print the output_str and return.
5. After that call the subsequence function recursively by removing the first character of input_str without appending it into output_str.
6. This also continues till the string input_str become empty.

Implementation

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Time Complexity

As the above recursive function is called total $2^{n}$ times as there are total $2^{n}$ subsequences of a string of length n. And in every function, we are doing work which takes a constant amount of time. So the complexity of every function is $O(1)$ and there are total of $2^{n}$ calls. So worst case time complexity of this approach is $O(2^{n})$.

Space Complexity

As we are using no extra space in this approach so space complexity is $O(1)$.

Algorithm 2- Recursive Approach by Removing Kth Character

Approach

In this approach, we will use a set to store all the subsequences. First of all, we will generate all the substrings of the string and then for every substring, we drop characters one by one and if the substring after dropping the character is not in the set then we again call the function recursively.

Algorithm

1. Start iterating over the input string input_str.
2. In every iteration start a nested loop for iterating the string from the end to generate the substrings.
3. Add every substring to the set.
4. Now start dropping characters from the substring.
5. If the string obtained after dropping the kth character is not in the set then recursively call the function.

Implementation

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Time Complexity

As in the above function, we are iterating over the string of length n and we are using a nested loop for an iterating string from the end. So for iterating two nested loops, the worst-case time complexity is $O(n^{2})$. And in every iteration we are inserting an element into the set, for inserting an element into the set time complexity is $O(logn)$ and we are iterating over substring for dropping character which has $O(n)$ worst-case complexity. So total time complexity of the function is $O(n^{2})*O(n)*O(logn)$ = $O(n^{3}logn)$ and total $n^{2}$ times function is called. So worst case complexity of this approach is $O(n^{5}logn)$

Space Complexity

As we are storing all subsequences in a set and the total number of subsequences are $2^{n}$. So space complexity is $O(2^{n})$.

Algorithm 3- Recursive Approach - by Fixing One Character and Making Subgroup

Approach

In this approach, we are fixing one character of the string at a time and then adding other characters for generating the subsequence of a string and if the current string length is not equal to zero then we print that string.

Algorithm

1. Start a loop for iterating over the string.
2. Add the present index character to the string and then call the recursive function for the new string.
3. If current string length is not equal to zero then print that string.
4. After returning from the recursive function remove the last character of the current string.

Implementation

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Time Complexity

Here we are using the concept of backtracking for finding the subsequence of a string. The worst-case time complexity of this approach of the subsequence of a string problem is $O(2^{n})$.

Space Complexity

As we are not using any extra space So space complexity of this approach is $O(1)$.

Algorithm 4- Using Bit Manipulation

Approach

In this approach, we are using bit manipulation to print all subsequences of a string. We will consider all the numbers from 0 to $2^{n}$ and for every number, we will check the set bits(1) and we pick only those index characters for which we have set bit. In this, every number gives us a subsequence. And all the subsequence of a string is generated.

Refer to the below image to visualize the bit manipulation approach of the subsequence of a string problem.

Algorithm

1. Declaring the list output for storing all the substrings.
2. Start a loop from 0 to $2^{len}$ i.e (1<<len) using the variable num.
3. For every value of num iterate a loop for the length of the string to check if the ith bit is set.
4. If the ith bit is set then we will add that character into the string.
5. If the string obtained after the inner loop has a length greater than zero then add that string into the resultant list.

Now first of all let us understand << operator.

Example: 5<<2 = 20 Binary conversion of 5: 00000101 When we left shifts the bits of 5 by 2 places then we get: 00010100 Decimal conversion of result: 20 $1<<len=1*2^{len}$

Implementation

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Time Complexity

As there are two nested loops and the outer loop runs $2^{n}$ times and the inner loop is running n times. Here n is the length of the string. So total time complexity is $O(2^{n})*O(n)$. So worst case time complexity of this approach is $O(n*2^{n})$.

Space Complexity

As we are storing all the subsequence of a string in a list and there is a total $2^{n}$ of the string of length n. So space complexity of this approach of the subsequence of a string problem is $O(2^{n})$.