Hi, everyone.
So today we are going to solve this problem, valid parentheses.
OK, so the problem statement is very simple.
So we will be provided with a string.
OK, so the input will be a string and the string can contain only six type of characters.
OK, so these are the six type of characters that the string will be made up of.
OK.
So these are six characters and the string will contain only these six characters.
OK, so we have to tell whether the string is a valid string or not.
OK, so for example, if they input this, so this is a valid string, so our output should be true.
OK, so we have to redone that type of the function will be OK.
So we have to return.
True or false, whether the parentheses is valid, whether balances are balanced or not balanced.
So in this case, our output will be true.
So in this case, so these two are merging again.
These two are matching.
So this is string.
These parentheses are balanced.
So our output will be true.
Now, in this case, our opening record is different and our closing record is different.
OK, so our output will be false here since the opening and closing record do not match.
OK, opening and closing records are different now in this case.
So this is my opening record.
Again, we have an opening record and then we have a closing bracket.
So this is wrong.
So this should be like this only.
OK, so that it matches the opening bracket so the output will be false.
Now, in this case, opening bracket again, opening bracket, now the closing bell.
So the closing bracket and opening bracket.
So they are matching.
So we will move ahead.
So now this is closing brackets.
So closing bracket is matching with the opening bracket.
So our output will be true.
OK, so that is the meaning of balanced parenthesis, balanced or you can say valid parenthesis.
OK, balanced or valid.
So our output will be a string and the return type will be a boolean value, true or false, whether
string is balanced or not.
OK, so how are we going to solve this problem so we can solve this problem with the help of Steg.
OK, so how stacked will help us to solve this problem?
So let's take an example.
So let's take this example.
OK, so let's take a bigger example to help us understand how the will work.
OK, so let's take the example of a valid string.
So we have opening record again, a different opening record, then a closing record, let's say, again,
opening Beckert, closing record.
So again, opening.
So this is closing and this is closing.
OK, so this is an example of a valid string.
So this is valid.
How this is valued, you can see opening and closing, they are merging again, opening and closing,
they are matching, opening and closing, they are matching and again, opening and closing, they are
matching.
OK, so basically our output should be true in this case.
Now, how we can use the help of Streck, so initially what we will do, so I will create a strike.
So initially our strike will be empty.
OK, so this is my steg initially, the deck is empty.
Now what we will do, we will iterate over the string.
OK, so I am standing here, OK?
So if it is an opening record, then I will push it inside the stick.
OK, so what are the rules.
So rules is if.
Opening record.
OK, so if you have an opening parenthesis, opening bracket, then push.
So this is very simple.
OK, so rule number one, if the beckert is opening, then they actually push inside the stack.
Now we will come here.
So, again, this is an opening record, then directly push inside the deck.
Now see, so now we have a closing bracket, so rule number two.
So if the bracket is a closing bracket, then what will do?
So if the bracket is disclosing bracket, then at the top of the stack.
The record should be this one.
OK, semillon.
If the closing bracket is this one, then at the top of the stack, our opening bracket should be this
one.
If the closing bracket is this one, then at the top of the stack, our opening records should be this
one.
OK, now, if the opening if the top of the stack is not this one, then I will simply return false.
Similarly, if the opening bracket is not this, then I will return false.
If the closing bell is this and opening in the top top of the stack is not this character, then I will
return false.
OK, so in this case we have this closing bracket now at the top of the stack.
We have its corresponding opening bracket.
Then what we will do.
So this is the case.
We have this closing bracket and the top of the stack.
We have this opening bracket.
So if this is the condition that we will do so.
I am writing here, if this is the condition, then simply pop.
OK, so we will remove this part.
And now let us move ahead, similarly here we will pop and similarly here we will pop.
And in the last part we will return for its OK and that's we will return fault.
Now, let us remove this, OK, so move ahead, we have opening bracket since we have an opening bracket,
likely push inside the.
Now we have a closing bracket.
So we have this closing.
Very good logic, the top of the stack.
So top of the stack is we have a similar corresponding its corresponding opening record.
So this is the case.
This is my closing bracket.
And the top of the stack I have, this is its corresponding opening bracket.
Then what we have to do, Bob.
OK, so we will pop.
Now, let us move ahead so I have this opening record now at the top of the stack, I have its corresponding
opening record.
OK, so OK, so sorry, we have opening backward.
So if we have opening record, we will simply push.
So this is.
Might this opening record no, I have a closing record, OK, so I have this closing bell now at the
top of the stack check whether it's got a smartening opening record, it is not as present or not.
So it's corresponding opening back of this present.
Then what we have to do, we have to pop.
OK, so I will pop this part now.
Move ahead.
So I have this closing record.
So this is the case.
I have this closing record now at the top of the stack, whether check whether it's corresponding opening
because there are not OK.
So it's corresponding opening bracket is there at the top of the stack.
If it is there, then we have to do we have to pop.
So I will pop and then we will reach the end of the string and that will strike is empty.
OK, so if our stack becomes empty after traversing the whole string, if our strike is empty, then
we will return through.
OK then only we have balanced parenthesis.
OK, if the state was not empty, so in the early part, we will return false.
So when the state will not be empty, for example, it is considered a situation.
So let's say our string is basically, let's say only this much.
OK, so we have only a single correct string.
So in this case, what will happen?
I will reverse the string fence.
This is an opening bracket.
So initially my map, initially my state will be empty.
So it's an opening bracket.
Then I will push, then I will move ahead.
So I westing will finish.
Now we will check to since the state is not empty, I will return false.
So in this case, I will return false because the stack is not empty.
OK, so these are very simple rules.
OK, so first rule is if you have opening record of any kind.
Then you can likely push if you have opening record of any kind, so opening record can be of obviously
three kinds.
So this one, this one and this one.
So if you have any of these three characters, then you will directly push inside the stick.
Now, if you have closing record, so closing record can be of three types.
OK, so closing bell.
Good can with this one.
Closing bell, good can with this one and closing record can with this one.
If the closing record is this fun, then at the top of the stack, so at the top of the stack, you
should have its corresponding opening record.
So if you have its corresponding opening record, then pop from the stack.
Otherwise, you can directly return false.
Are there ways you can like it unfolds and similarly with these characters?
OK, now let us see the example of Foyt, so let us take Invalid's String.
So let's say our string is basically so this is opening record and this is Lizzi closing record.
Now let us out of the string.
So at this point.
So this is an opening record.
What we will do, we will push inside this deck.
So I will push the opening record.
Now, come here.
So this is a closing record and closing record is of this one kind.
OK, so if this is the closing record, then at the top of the stack, I should have this one opening
record.
Now check the opening record.
So opening record at the top of the stack is different.
Since it is different, I will likely return for it.
So I will return files, which is the correct output.
OK, so what do we the time and the space complexity, so time, complexity is very simple.
We are just iterating over the string of time complexities when and the space complexity we are creating.
So the space complexity will be on.
OK, now let's write the code.
So basically this problem is present only at code.
OK, then the problem is valid parentheses and these are some examples.
OK, so now let us write the code so what we have to do, so first we have to create a stack.
Now, the tape will store characters, OK, stack monster characters and let's say the name of the stackers,
so let's change the name of the string to be a and then able to strike us as OK.
So what we have to do, we have to simply iterate over the string.
OK, so let's say straight or the string.
We will pick each character, so.
I am outrating over Distin.
Now, our first rule, so if I have opening bracket, then we can actually push.
OK, so.
If we have opening markets opening, Beckett can be of three kinds.
So or a call, the second type of opening record.
And similarly, the third type of opening record.
So if you have any of these three opening records, then what we will do, we will push inside this
track, we will push this character inside the stack.
So as push off a.
OK, now in the L'ESPRIT, now we have closing records.
OK, so if we have closing records.
What we have to do, so first of all, let us check.
So if the stack is empty, then we can simply return false.
OK, so if the deck is empty.
What you can do, we can simply return false.
OK, so this is important to right here.
I will explain it later, why it is important to write this line, OK, that you will get runtime error.
OK, so important otherwise.
Reintegrated.
OK, I will explain it later after writing the complete code.
OK, now what you have to do.
So we have closing the code at this point.
Now let's check.
So if.
Now, let us write elusive, so the elusive part or two, all right, so if HFA is now, we have two
types of closing record.
So I have this kind of closing record, then what I have to do, I have to check the top of the stack.
So if.
Startup.
A consequence, its corresponding opening record.
OK, so its corresponding opening record is this one.
Now, if this is the case, what I have to do, I can I will simply pop.
I can simply park while I can simply pop and in the part I can return false.
OK, so we we will do.
The similar with the other opening, other closing records.
Now, if the opening record is of second kind, this one, then it's open, then at the top of the stack,
I should have this one record.
Astarte, Barback, and similarly.
I should have this one.
OK, so and when the string will finish.
So after outrating over the computer string, so after a complete string, I have to check whether the
string, whether this tank is empty or not.
OK, so at this point, I will check.
So if.
The steak is empty.
Then you can simply return to.
Otherwise, this is not a valid parenthesis we can return false.
OK, so let us run our good.
OK, now let's try to submit.
OK, so our goal is working fine now.
Let us try to understand our code, OK?
So basically, this is our rule number one.
OK, so this was our number one, that if you have opening record of any kind, the nightly push inside
the stack.
OK, so no difficulty.
Now, let us explain this line, why this line is important to right here and otherwise I will get.
So this is runtime error.
OK, now let's say our string is basically it is consisting only of closing brackets.
OK, so I let's it is it consists of only closing.
So what should be our output at this point.
Obviously our output should be false.
This is not a valid string.
OK, valid point is, is that not there.
So now let us try to execute our.
What will happen.
So this is our stack.
I was taken initially and I am standing at this point.
OK, so this condition will be false.
So I will go to the Elzbieta part.
So inside the LS part of this line is not there.
OK, so if this line is not there, then what I will do, I will execute this line.
So if I equals equals closing record.
No, this is not this type of closing.
I could know this type of closing record.
Yes.
So I will execute this part.
Now it is written here.
So if you, if you will see carefully I have written as top ecological opening record.
OK, so I have written as the top inside the if condition as the top opening record of this kind.
So now see, the stack is empty.
Stack is empty and basically what we are trying to do here is you are trying to get the top element
of the stack and the stack is basically empty at this point.
So what will happen?
You will get a random error because you are trying to access the first element of the stack, the topmost
element of the stack and the stack is basically empty.
So that's why you will get married.
So first, accessing so before accessing the top element, you have to read this condition.
OK, before accessing the top element, this condition is mandatory to read, you can update this condition
also.
OK, so what I'm doing here.
So before going inside this elusive part, I'm checking first.
I'm checking first.
If the steak is not empty, then then you perform this operation and the steak is in pretty badly written
defaults.
OK, so it is very important before accessing the topmost element.
First, you have to check whether their stack is empty or not.
OK, because of the stack was the stake is empty.
You will get at it.
OK.
So I'm repeating myself, what is the problem?
So you want to access the top element of the stick?
OK, now there are two cases.
Either the top element exist or the top element doesn't exist.
So if the top element exists, it will work fine.
Now, if the stack is empty, so if the stack is empty, element will not exist.
And at this point you will get married.
So that's why I first you have to check where the stack is empty or not.
So you can also write it like here.
So first I have to check.
So if this tag is not empty.
And.
As top equals equals this opening record.
OK, so you can write like this first, I am checking if the stake is not empty and then I will execute
this part.
OK, so you can also write this and then you can remove this part if you want to.
OK, so how this will work.
So basically what is the meaning of this line?
So this line says if the steak is not empty.
OK, now there are two parts of the state will be empty or it will not be empty.
So if the stack is empty.
Then I will not execute the second part, I will not execute the part after the end.
OK, so this part will not be executed, so we will not get married.
So runtime error will not be there because this part will not be executed.
OK, and if the bag is not empty, so Steg is not empty.
If the steak is not empty, then I will check the second condition and obviously if the steak is not
empty, we will get the top element.
So, again, our goal will work fine.
OK, so instead of writing and the steak is not empty and every condition I decided to write at once
here.
OK, so instead of writing this condition with every condition, with every condition, I decided to
write at once at the starting of the loop.
At the starting of the conditions, ok.
So I hope this court is clear.
OK, so if you have any doubt in this problem, you can ask me sort of the space complexity.
Time is linear and space is also on.
OK, thank you.