Hi, everyone.
So today we are going to solve this problem, remove all our duplicates, character in a string.
OK, so what this problem says is this problem says jus.
The word dissent obligates and let them choose to dissent, duplicates and believed them.
OK, so remember to add dissent and duplicates.
OK, so.
My input will be basically a string and output will also be a string.
And this string will not contain duplicate characters.
OK, so let's consider let us take some input and output example to understand the question.
OK, so here would have to choose, choose to discern, duplicate and delete them.
So these are two different duplicates.
So we will delete them.
So my output will be a B, OK, so Mark will be only now in this case I have to choose two different
duplicates.
So these are two adjacent duplicates.
These are two different duplicates.
And similarly, these are two different duplicates.
So I will remove them.
And my output will be A, B and B, OK, so this is my output.
Now let's see this example.
So this is my input.
These are two adjacent duplicates.
So I will remove them so my output will be empty string.
OK, so my output is basically empty string.
Now, let's consider this example.
So these are two adjacent duplicates.
OK, so what will happen?
I will remove them.
So after removing them, what will be my string?
So my string will become B, B?
Now, again, these are two adjacent characters, so I will remove them so my output will be empty.
String.
OK, Margaret will be an empty string that are disconcert.
Then one more example.
Let us consider this example.
OK, so these are two different characters so I will remove them.
These are two different characters.
I will remove them.
These are two different characters.
I will remove them.
So what will be my string.
So my string will be m i again.
I again I again I.
OK, so what will happen now.
So these are two different characters so I will remove them.
These are two adjacent characters.
I will remove them.
So basically my output will be m OK.
So I hope you understood this question.
So this question is basically pleasant only.
Good.
OK, so let us understand this example also.
So I have this string A, B, B, a, c, a.
OK, so these are two different characters, so I will remove them.
So what would be my string.
It will be a a c e.
Now again, these are two distinct characters so I will remove them so I will become CI a..
So this is my output.
OK, you can see, see is the output.
OK, so we have to remove the word just ten equal letters.
OK, so two different letters.
We will find out and then we will include.
OK, so you can read this line.
So we will repeatedly make a duplicate removals.
OK, we will remove duplicates on string until we no longer can.
OK, so now let's see how we can solve this question.
So the very simple approach and the very good approach to solve this question is with the help of a
map.
OK, so how we will take the help of a map.
So let us consider.
This example only.
OK, so let us consider this example so.
I have this string and I is is A is is A, B, B, I, so I have this string.
So the very good approach to solve this problem is with the help of a stick.
So what I can do, what I will do, so I will have a string.
So initially my stake will be empty and the state will be of character.
OK, so I will have a stack of characters.
Now, I would like to draw the string.
OK, so now let's get it over this string.
So the first character is M and my stake is empty.
Since the stake is empty, we will push.
OK, so here comes my first rule.
What is the first rule?
So if the stake is empty, nest egg empty, then push.
OK, e-TAG and President Bush, so this is my first full.
Now, I will come here.
I so now steak is not empty, so this is not the case.
So I will come to situation number two, OK, steak is not empty.
Now compare I with m OK, so these two are different.
That means I do not have to remove anything.
So what I will do, I will push I so what I'm doing here compared let's say the name of the string is
E to compare E of A.
With the top of the stick.
OK, so I'm comparing a with the top of the stack basically stack top and if these two are not equal.
OK, so if each US is not equal, so stagnant up, then again, Bush.
OK, so I am pushing.
I hear.
OK, so now as now the situation will be static is not empty and the top basically of ibises is not
equal to not dubstep not is I.
So I will push through as will go inside now.
S ok so S and s nowadays image.
So this condition is not true, this condition is not true.
So I can do condition number three.
So if there is a match then pop.
If there's a match, then pop and move forward.
OK, so very simple.
So what I will do, I will pop from the.
So let us pop from this track and move forward.
Very simple.
Now.
I and I, again, condition number three will be executed, there is a match if there's a match up and
move forward.
So I will pop and I will move forward.
Now, compare s with M, so these are different s and are different.
So basically this condition will be executed.
I will push as so my stake will be.
So let's say this is my steg, so I have M and I will push.
So that is s OK now again so s and top they are equal if they're equal.
So pop and move forward.
I and they are different than Bush I.
OK, so B b and they are different than Bush B.
Again, B, so B and B, they all seem so conditioned, three, pop and move forward, so let s pop.
And move forward.
So I and I, they all seem so conditioned, but try and move forward so pop and move forward, OK,
so when we will reach the end of the string, so this is basically the end of the string.
So virtually my answer.
So my answer will be present inside the stack.
So my answer is basically am.
And M is the right answer.
OK, let us consider one more example to understand it better.
OK, so.
Let's consider this example a BBC.
OK, so I have this string A, B, B, E, C and E.
OK, so I have this track.
OK, so now let's hydrate.
So my steak is empty.
The steak is empty, we can directly push now B, so B and E, they are different than Bush B.
Now be so be and be stacked up and the current element equal, so I will pop and move forward, so pop
and move forward.
So easy and a stacked up and current vertical, then pop and move forward.
So I will pop and I will move forward now see and my stomach is empty.
So at this point, my stomach is empty.
So the steak is empty.
I will push.
See, OK then.
So compared with the stacked up, they are different than Bush.
Then I will reach the end of the string.
OK, so I will reach the end of the string.
And now my answer is this one.
So basically, when we will pop the element, he will come first and then he will come first, but then
I have to reverse this.
OK, so I will reverse this.
And my answer will be, see, OK, so this is the correct answer.
OK, so when I will pop, it will come out first, then she will come out first.
So to get the answer, to get the answer, I have to apply the reverse operation.
Then my answer will come out to be.
OK, so I hope you understood this question.
So what will be the time and the space complexity.
So basically the time complexity we are just getting over the time complexities when and similarly the
space complexities big off and we are creating stack.
That's why the space complexity.
OK, so if you have understood this question now, let us write the code.
OK, so first of all, what we have to do, we have to create a stack of characters, OK, and let's
say the name is now what we have to do, we have to iterate over the string.
OK, so let's go straight over the string.
So I called societal iList, and he says.
And they placeless.
OK, so condition number one, what is the condition, number one, if Steg is empty, then we can directly
push.
OK, so if a steak is empty.
If there's anybody we can barely push or there is one more condition for pushing.
You can see.
OK, so we have two conditions for pushing these two other conditions for pushing the element, and
this condition is for popping the element so the steak is empty or the current element is not close
to the stacked up, then push.
So I can see if the current element, which is Alphie, if the current element is not close to stack
top element, so stacked up element, then what I have to do, I have to simply push.
OK, so Astarte push.
Alfy.
Now, in the last part, what they will do will simply pop up and move forward so as to pop and move
forward.
OK, so from moving forward, I have written C++ here.
Now, finally, what will happen, so there is strength, so now let us construct our answer.
So initially my answer is empty.
OK, so I'm listing initially my answer is and listing.
Now you can see here.
So how to get answered.
So my answer is present inside this stack.
OK, so what I will do, I will pop every element outside the step toward popping the element.
I will like I will pop every element from the stack so my string will become easy and then I will reverse
the string to get the answer.
OK, so I have to reverse.
Remember, now let's remove the element from the stack.
So while Steg is not empty, but I have to do I have to pop element.
So basically Sadaat pushback.
Alphie, sorry, I thought I'd push back top.
So after getting the element from the top of the stick, we will pop that element.
OK.
So while steak is not empty, I'm getting the topmost element and then I am popping that element.
Now, finally, what we have to do, we have to apply the reverse operation so far, reversing either
build, function, reverse, so reverse onslaught begin.
I am reversing this string, so reverse order to begin karma, so God and I have to give 2.0 beginning
and appointer.
OK, so to iterators and finally the return diaper's string.
So I will return my answer.
OK, so let's run code and then we will try to submit our code.
OK, so now let's admit.
OK, so our goal is working fine, our goal is 100 percent correct.
OK, so basically the same question is also president on Heckerling.
OK, so Gorenc is also a very good website if we want to prepare.
So this is exactly the same question.
The name of the question is super produced a string, OK.
So now let us summiteer also, so I'm copping the gold.
And let's put the gold here.
OK, so this is String S, so we have to change the name string.
OK, so here the name of the string is a.
So that's why I have to change the name of the string.
OK, so now let us first we will run code and then we will submit.
OK, so I forgot to tell you one thing, so here you can, if you will, read the question.
So the question is, so the question is you have to print emplacing, OK, so I have to print these
things.
What can I do here is so first of all, I will check the size of it.
So if the size of it.
So if you're not sorry if I said what size.
Equal, equal zero, basically, the strength is empathy then would have to return.
So I have to return empty string.
OK, so we can copy from here.
So I have to return empty string.
If that if the size of this string is zero of the size of our own zero, basically this thing is empty,
then I will return empty string.
OK, so these are the simple test cases, so our court passes on a simple test cases.
Now let us try to submit our call.
So there are 15 test cases on knackering.
OK, so our goal is working on all the test cases.
OK, so our goal is working.
Now, the time and the space complexity we have already discussed, so basically the time, complexity
and these are the time and the space complexity.
So what we can do here is we can optimize this space complexity to the order of one, OK?
We can optimize the space complexity to the order of one.
How so?
Basically what we will do so here, what we are doing here is so here in this cold, in this cold,
what we are doing, we are creating stack explicitly.
OK, now what we can do, we will write code in such a manner that our code will work as a steck.
Basically, what is the property of us?
So instead, I have only one point, which is the top point.
OK, so I have a pointer top and this top window is doing all that thing.
OK, if I'm popping the element at this point, I will come down and if I am pushing the Aylwin this
point, they will come up.
So basically the stake is melting.
It is just appointer.
So what I will do, I will maintain appointer.
I will maintain aspect of pointer and then we can write this code without explicitly creating a stick.
So for example, what I will do.
So let us consider this example.
Only ABC.
So I have this pointer A B, so I have this string abebe e, c, e.
OK, now what I'm doing here.
So initially, my stack pointer is here, so when I come here, what did I see?
If the stack is empty, then push, OK?
And then first of all, this checkpoint, I will come here and then I will push.
OK, then I will compare B with this stack top pointer.
So basically I will create a stack of pointer and this pointer stack pointer, it will be initially
minus one.
If I have to push the element which I will do so I will do stack pointer plus plus and then I will push
the element of first let me write the code and then I will explain it to you so that you can understand
it better with the help of code.
OK.
So will write very similar called.
So first, let us commend this good.
So our goal will be very similar, but what we are trying to do here is so I am trying to stimulate.
In places like.
So first, what we are doing, we are trading over this string, but first of all, I have created this
is so greetings deck means basically appointer.
So I have this deck pointer, which will be initially minus one.
OK, so empty means minus one.
So I have to point out which is initially minus one now radarscope it is called.
OK, so I'm copying this code now, I'm meditating over that.
So if Stack is empty, stack empty means.
Standpoint, that is minus one.
OK, so stack and stack, pointless minus one.
So if stack pointer is minus one.
OK, so this is the condition now, the second condition, if the current element is not close to the
topmost element.
Now how to get topmost element.
So basically we have stack pointer for that.
OK, so aof stack pointer.
OK, now let us see, it's not Bush, we are pushing the element, OK, so for pushing the limit, what
we will do, we will.
We are pushing the current element so far, pushing the limit.
First we have to incrementalists pointer and then we will push.
OK, so for pushing off Stack pointed.
We are pushing the current element.
OK, we are pushing the current element.
Now, let's see.
So here in the old part, what we are doing, we are popping the element.
So popping means stack pointer, minus, minus.
OK, winter minus minus, then what we are doing, so we are taking a strong answer now let's take answer
here.
Which is initially empty, and then we are creating our answer from the spec element present inside
this deck.
OK, so how many elements are present inside this deck?
So stack pointer will tell us.
So these are the number of elements which are present inside this deck and I placeless.
Now, let us construct our answer, so I said our pushback got most relevant.
OK, so we are pushing elements.
So it will be basically.
It will be if I OK, and here we do not need to reverse anything, so we will likely have done our answer.
So now let us try to submit this call.
OK, so our code is working fine.
OK, so what is the time and space complexity of this cold?
So basically, the time complexities, Lynnette, and here, the space complexities my violent, because
we are not creating a nest egg, we are trying to simulate the stack in place.
OK, so let's see how this code is working.
OK, I will try.
I will tighten the code on this example.
So I have this example A, B, B, A, C and A, OK, now this line stack pointer is minus.
OK, so these are the indexes.
Zero, one, two, three, four and five.
These are the indexes.
OK, so Stack won't lose initially minus one.
So suppose this is minus one.
So initially this is my stack pointer.
ESP means stack pointer, ok.
Now what we are doing we are iterating already if the pointer is minus one.
So we are getting all the idea.
So this is the value of a OK, so I decided OK, so this is the value of.
So first we are checking effect.
Pointer is minus on the stack is empty just like above.
So the stack pointers minus one.
Yes it is then stack pointer plus plus and push the element.
So stack pointer plus plus that means stack pointer removed from here standpoint will come here.
OK, and then, Ágúst, that point, that is IAFIS, so basically replace a with a look now I placeless
so I will come here.
Now, be OK, so standpoint does not my Nesson, then I'm comparing the current element with the element
present at the top of the stack.
So the current element is B and element present at the top of the staircase.
However, because you can see stack pointer is pointing towards A, so B and E they are different.
If they are different, stack went up plus plus basically we are pushing the element so remove.
Standpoint plus, plus and then push the element to replace B with B, now A plus plus.
So I will come here now compare the current elements.
So I'm comparing the current element with the top last element of the stack.
So I'm comparing the current element with the topmost element of the stack.
So they are saying if they are same standpoint, minus minus to the stack pointer.
Welcome here.
Stack pointer, minus minus stack point only, come here, so remove this and I will do a placeless.
OK, now compare the top most now compare the current element with the topmost element of the stack.
So there is a match.
OK, again, there is a match, so I will lose track of minus minus here.
I am comparing the current element with the topmost element of this track, which is a.
So there is a match stack pointer minus minus.
So stack pointer remove stack pointer from here and again it will point towards minus minus.
So this is my stack pointer.
OK, now I placeless so I will come here.
So this is, I know the when there is minus one.
Basically the stack is empty so the stack is empty.
We can directly push so far pushing first we have to increment and then we will push the element.
So increment.
So stack pointer will come here.
So remove it.
So this is stack pointer and what we are pushing the element.
So aztek pointer is alphie.
So replace this E with C, so C will come here.
OK, now I placeless, so this is a now compare the current element with the topmost element.
So this is stack pointer and this is the topmost element, which is basically C compare it with the
C, so they are different stacked one plus plus basically we will push the element to stack one toplessness.
So step removed from here and this will become stack pointer.
And for pushing the element replace B with A.
OK, replace me with a then we will reach the end of the string, so after reaching the end of the string,
I am constructing my answer and what I am doing.
So I am I am starting from zero till stack pointer.
We will push the limits.
So what is the value standpoint?
What a value point that is basically one.
So stack pointer is one.
So what I am doing starting from zero point also basically starting from zero point which is one, so
basically zero and one only.
I am pushing the elements of I inside the answer that string.
It has been what if it has been modified.
So these are at zero.
I have three add one.
I have a so I will push three and a.
So at index zero I have C.
I had the next one I have E and then I told you there is no need to reverse.
OK, so we are currently getting our answer here so there is no need to reverse.
And this is my answer second and then I am returning my answer.
OK, so I know initially this is very overwhelming.
OK, so for you, I know I have to go into the same situation.
This is very overwhelming.
But if you will try to compare this cold with this cold, it is very similar.
OK, so I hope you have understood this cold.
So if you don't know this cold, OK, so if you are not able to understand this cold, no problem,
OK?
So this cold is really good.
OK, this cold will pass all your discusses.
This cold is really good, but if we want to optimise then this is the way to optimise.
OK, you will see this approach in many, many questions.
OK, this is appointer approach.
You will see this approach in many questions.
So if you have any doubt in discussion, then please ask.
OK, and my suggestion will be please take an example and run this cold.
OK, take the example of Mississippi.
OK, so here I have discussed the example of Mississippi, so take the example of Mississippi and try
to rent this good OK standpoint simulating in plastic.
OK, so this cold is very, very good.
So what is the time and the space complexity.
So the time complexity is when and the space complexities even.
OK, so I will share the call with you.
Thank you.