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