Being a significant and fundamental concept of coding, the concept of strings holds a significant weightage in your exams and interviews as well. Programmers have to deal with questions related to strings every day and this is why revising your concepts frequently is very important.
When it comes to strings, different operations and sub-concepts are included under them. One such common concept is a subsequence. A subsequence is a part of the string that you can derive either by deleting none or multiple elements of a string without changing the order of the remaining elements.
But how do you find the subsequence of a string? Well, if you are not familiar with it, this post is what you need. Check out in detail what is subsequence and how to find one.
What Is A Subsequence?
Before understanding how to find a subsequence, let’s understand what is a subsequence of a string.
A subsequence is defined as the sequence derived from the given string after removing multiple or no elements of the string keeping the position of other elements the same.
To make it more clear, consider the following example:
You are given a string S= abcd
The subsequences of this string will be: a, abc, ab, abcd, bc, bd, bcd, cd, d, b, c
Hopefully, now you are clear of what a subsequence of a string is. Now let’s proceed with how you can find the subsequence.
How To Find All Subsequences Of A String?
There are two possible methods to find a subsequence of the string. They are
- Through bit manipulation
- Through recursion
Let’s dig deeper into both methods in detail individually.
Through Bit Manipulation
To perform the bit manipulation method, the first thing that you will have to do is to check if the ith bit is a set or not.
In case n and (i>>1)!=0, it implies that the bit is a set.
When done, you will have to note down all the numbers ranging from 0 to 2^(n)-1. Also, note down the bit representation. If it is 0, it means the character is not picked and if it is 1, it means that the character is picked.
In the same way, we need to traverse completely from 0 to 2^(n)-1. Here, we need to check in case the bit is a set or not. In case it is a set, you need to add that character to the subsequence.
Complexity Analysis
- Time Complexity: Since we are using O(2^n) for our outer loop and O(n) for our inner one, the time complexity of this method is calculated as O(2^n *n).
- Space Complexity: Since no additional space is being used, the space complexity of this method is calculated as O(1).
Through Backtracking or Recursion
Now the next approach you can use to find the subsequence of a string is using the backtracking method. Now in this process, we will be generating two subsets which imply that two cases are possible. Either you will pick the letter or character or you will not pick it up and move to another one.
To perform backtracking, you need to follow the following steps:
- First, create a temporary string and keep it empty in the beginning.
- After this, you will have two options. Here, you can either pick the character or leave it and switch to another one.
- Make sure that you first pick the character at i and then go to the next index of the string.
- Now, in case you have filled the base condition which is i==s.length(), you will have to print the temporary string and then return its value.
- Other than that, while performing backtracking, we need to pop out the last character of the string in order to implement the condition of non-picking the element. Simply then proceed to the next position.
Complexity Analysis
- Time Complexity: The time complexity of this method is calculated as O(2^n).
- Space Complexity: The space complexity of this method is calculated as O(n) because of the temporary stack we are using.
Now that we are discussing common problems related to strings, one more problem that you can encounter is finding the nth character in decrypted string. Let’s take a look at this problem as well.
How to find the nth character in decrypted string?
In this problem, you will be provided with an encoded string. In this string, the repetitions will be represented as substrings which are followed by the count of substrings. You are required to find the value that will appear at the nth position of the decrypted string.
To understand better, consider the following example:
You are given an encrypted string S= “ab2cd2” and n= 4
The output of this program will be b.
Explanation:
The decrypted string of the encrypted string will look like this: S = “ababcdcd”. Here, the 4th element will be b.
To find the nth character in decrypted string, you will have to carry out the following steps
- To begin with, you will have to initialise an empty string.
- You will then have to decompress the given string by checking the substring and the frequency of each substring. Now, append your current substring in the decrypted string according to its frequency.
- Simply repeat this process till you reach the end of this string.
- In the end, print the nth character present in the decrypted string.
Conclusion
Subsequence is one of the most asked concepts related to strings and is a quite an extensive topic in itself. To find all the subsequences of a string, you can either use the bit manipulation method or the backtracking method.
Generally, the backtracking method is mostly used because of its simpler approach and less time complexity. However, in this approach, more space is required. Therefore, check out both methods and choose the one that suits you.
Also Read – What is Modular Exponentiation Method?
