Are you preparing for a programming interview? If so, you would already know that learning data structures and algorithms alone will take you down the success road.
However, after you learn DSA concepts, you must well-prepare yourself with regularly asked questions which will be related to,
- Arrays
- Strings
- Binary Trees
- Graphs
In this article, we’re going to specificall learn about how you can print all subsequences of the string. To understand this complex and highly repeated question, we will provide a sample problem along with solution methods. Head on and learn about one of DSA’s fundamental concepts.
What is a string?
A string is an arrangement of letters and numbers that are interpreted by a script. An example of string would be “STRING234”
Some of the library functions of strings which can use are:
- Strcat: Helps combine two strings.
- Strncat: Helps combine N elements of a string to another.
- Strlen: A string’s length is returned through this function.
- Strcpy: It helps in copying a string from its source to its destination.
- Strncpy: Copies N characters.
- Strcmp: Joins two strings and determines the values.
- Strncmp: Similar to strcmp but compared N characters initially.
- Memset: Initiates a string for all nulls.
What is a subsequence of a string?
If you want to know how to print all subsequences of a string, you should know what a subsequence is.
In a string, a sequence denotes the number of characters which can be derived after removing zero or more elements without disturbing the remaining characters’ order.
An example would be:
Input:
Str = “zz”
Output:
Z
Z
ZZ
Explanation: Firstly when we generate a subsequent after deleting 0 characters, the subsequence we will get is “ZZ.” Then, we will delete one character and the subsequences would be two in number, that is, “Z” and “Z”. Once we delete two characters from the string, the subsequence generated would be empty/null.
DSA Fact: In a longest subsequence palindrome, we will figure the characters within a string that pronounce the same even if it is written backwards. In the string BANANA, the longest subsequence palindrome would be ANANA because when it is spelled in reverse, it is again ANANA.
Methods to print all subsequences of a string
To solve this problem, programmers are benefitted with four noteworthy solutions. Below we have compiled all the necessary steps for each method, take a look at them.
Pick and Don’t Pick Approach
In this method, we first take the first element of the input string and append it. After that, we call the subsequence function until the string becomes null. Then, we again use the subsequence function but this time we will not append the first element of the output string.
Steps:
- Create an input string and output string.
- Remove the input string’s first element.
- Call the subsequence function by appending input_str first character.
- When input_str becomes null, print output_strn and press return.
- Similarly, now call the subsequence function without appending input_str first element to output_str.
- Continue until input_str turns empty.
Time and Space Complexity:
As we include the recursive function, the time taken is O(2n) and as no extra space is utilized, the space complexity would be O(1).
Recursive approach – remove Kth character
We will make use of a set to save all the subsequences in this method. We will generate the substrings of the input string then for each substring, we will remove the elements one by one.
Steps:
- Initiate iteration on input_str.
- Then, for every iteration, initiate a nested loop. It will iterate a string from the end and will generate substrings.
- Now, add the substrings to the set.
- From the substrings, drop out the characters,
- If the string found after removing the kth character seems to not be present in the set, then apply a recursive function once again.
Time and Space Complexity:
In this approach, we iterate over length n’s string and we also make use of a nested loop. As we iterate two loops, the time complexity is O(n3 logn). Due to storing all the subsequences within a set, the space is O(2n).
Recursive approach – fixing a character
We will fix one character within the string and then include other characters to get the subsequence. If the generated string’s length seems to be unequal to 0, then we print it.
Steps:
- First you should initiate a loop that will iterate on the string.
- Recursively call the new string once you add the current index character to it.
- If the string’s length is < 0, then print it.
- After the recursive function ends, delete the current string’s last character.
Time and Space Complexity:
In this approach, we implemented the backtracking concert. The time complexity is O(2n). Due to no additional space being used, the space taken is O(1).
Bit Manipulation
Using this method, we will take account of the numbers and for each of the numbers, we will analyze the set bits (1). After that, we will pick the index characters that we have a set bit for.
In this method, we get a subsequence for each number and finally, we will get the string’s subsequence.
Steps:
- First you should create an output list where you can save all the substrings.
- Now using the variable num, start a loop for (1<<len).
- For every num value, initiate a loop for the string’s length. Now check if the ith bit is set. If the ith set bit is ready, then add that character to the input string.
- Now if the derived string’s length after the inner loop process seems to have a length larger than 0, include this very strong to the output list.
Time and Space Complexity:
Due to the runtime of the nested loops (both outer and inner) we will get a time complexity of O(2n) * O(n). Now that we’re storing the substrings in a list, the space taken would be O (2n).
Conclusion
From sentences in books to phrases in your smartphone, strings is a concept that is seen everywhere. We hope with our article, you’ve got a deep insight to print all the possible subsequences of a string. If you have any other doubts, feel free to check our website.
