Hello and welcome back.
So in this video we are going to continue our discussion on recursion and string.
And now start solving some questions.
Now before we move on to the questions which are going to be medium to hard level and the type which
you can expect in companies like Google, Facebook and all these tier one companies, we have to understand
few things and differences between commonly used terms.
So first let's get started and understand them okay.
Now this term you can see written in front of you as well string substring and subsequences.
So string.
We all are aware string is something just like an ABC right.
Now what exactly is a substring okay.
What exactly is a substring?
A substring is actually when I say that ordering should be maintained.
Ordering to be maintained.
And it should be continuous.
So let me explain you with an example that what are different substrings of ABC gonna be.
Now for ABC the substring is gonna be a b and c ab bc CA.
Now CA is not going to be the substring.
The reason for that, it is not going to be the reason for that is I mentioned that ordering to be maintained.
Okay.
So we have this A, B and C in each and every thing.
You will see that okay.
Order is there.
Now these are actually some part of my string right.
Substring is some part of my string.
But the condition is that it should A maintain its order.
So you cannot have C and A okay.
And it should be continuous as well.
So you cannot just skip any character.
So you can take A and B.
That is fine.
You can take B and C that is fine but you cannot skip anything.
So that is the second condition which should be continuous.
The first condition is that ordering should be maintained.
So you cannot take B or A or C b.
Now, in a very similar manner of course a b c is also a substring, right?
So a b c is also a substring.
And that is how substrings are defined.
You can maybe think that okay they are connected with a string which you cannot cut.
So either you can take any of them okay.
But you cannot cut or leave out anything in between right.
That is why they are continuous.
Right?
So this is what substring is.
Now moving forward next is subsequence.
Now for subsequence order should be maintained.
Order should be maintained.
And they can be non-continuous.
Well they can be non-continuous as well.
So with the same understanding for a, b, c we have a, B and C ordering is maintained.
AB, BC and CA.
Okay, sorry not CA, AC.
So AC is true because here it can be non-continuous.
So I can take a, I can take a and then move to C.
That should not be a problem.
But CA is not possible because order is something which I have to maintain.
Order is something which I have to maintain.
And then of course the whole string which is going to be a, b, c okay.
We also continue as an empty set here.
So we I am writing this and this is normally an empty set where you are not taking anything.
Okay.
So many places consider the subsequences and subsequences is empty set as well.
Now the reason I am telling you these things is that along with understanding what they are, we will
try to understand few patterns when we solve these problems.
The reason for that is many problems which you are going to do right.
As I have already told that they are medium to hard level and I am going to give you the assignment
on the basis of same problem.
Now we do not have to run behind solution.
We have to make sure that we get our in-depth understanding and intuition clear, because these are
the kind of problems which are actually asked in the tier one companies like Google, Facebook, Microsoft,
and they are majorly focused that you should understand and solve similar kind of problems.
So you will majorly be making sure that you understand the in-depth intuition.
When I am writing the code, as well as when I'm explaining you the same.
Okay, so with that, just also let us see one more thing.
How many substrings are possible?
I think number of substrings possible are n into n plus one where n is my length of my string.
Right.
So for ABC you can see that six are possible right 123456.
And this is three into three plus one divided by two.
So it's going to be two right.
So it's the answer is six.
Similarly for subsequences the number possible is two to the power n.
The reason for that is we for each and every character we have two choices.
Either we can take it or we can not take it.
So this is something which you have done in permutation and combination as well, right?
So finding the subsequences substring, they are nothing but some permutation and combination of a string.
So for each and every character we have two choices.
Either we can take it or we can not take it, and hence it becomes two to the power n.
Now the same will be helpful when you will be solving similar kind of questions.
Okay, so let us move forward everyone, and let us try to solve the very first question which is going
to be we have to calculate or we have to find all the subsequences of a given string.
Right.
So we have now understood what exactly sub sequence and sub string are.
Now let us do this question.
Please make sure that you always focus on the understanding right.
So let's start everyone.
Let us start everyone.
First let us see if it is a B, c right.
If it is a, b, c, What is going to be the answer.
So we have just seen that A, B and C, AB, BC and CA.
Oh sorry.
My bad.
Not c I always write CA AC, then a BC and an empty set.
Right?
So this is going to be my answer everyone.
Now if you will see here exact some similar thing is happening.
We are taking something or not taking something.
So we are able to understand that something of a permutation and combination is happening.
So what I want to do is I want you all to first try out this question once.
Okay?
So let me give you the skeleton of this.
What we have to do.
So this is string substring and subsequences.
You will be given a string ABC.
Let us say we are taking ABC only.
You have to make sure that you return to me.
So return subsequences.
So given a string, you have to just return to me all the subsequences of this particular string.
Okay.
So try to do the same.
Try to do it once.
Try to write the code, understand how it's going to do.
And in the next video, I'm going to make sure that I write the code and explain you everything.
I can just give you a little bit hint the steps are going to be the same.
Find out what the base case is.
Okay?
What exactly is going to be the base case?
Try to write down the number of subsequences for a single or a zero digit string, or sorry, zero length
string.
Then see what you can ask recursion to do.
Can the problem be broken down into smaller part?
Try to see if for ABC you can find the subsequences of BK and then work on that.
Then get all the subsequences and in the end do your work okay.
So now you know enough recursion.
Now you all are semi mastered in recursion.
You have enough idea on that.
Try to just apply all the all the things which I have taught you.
Just do the application and make sure that you are able to apply it properly.
And maybe we can code the answer and get it nicely.
Okay, so cool everyone, let's meet in the next video where I'm going to show you the solution.
And meanwhile do give it a try okay?
Thank you.