Hi, everyone, welcome back.
So in this video, we are going to solve this coin flip and let's discuss what this question is about.
So it is saying you have a string nard string, you have a binary string by no means, zeros and ones.
So you have a string and it is containing zeros and ones.
Right.
So you need to figure out two things left and right.
So left means left index and right index.
So after figuring out that this is left index, this is right index, what do you do?
You will flip all the values.
So for example, this is your left and this is your right and left.
These are zero one and one.
So what you will do if you are saying this is left and this is right, you will flip all the values.
So this is when it will become zero.
It will become one.
It will become zero.
It will become one.
It will become zero.
So that is the meaning of flip, right.
Flip means convert zero to one and one to zero in the range L2 are so given the string lozzi, given
the string.
And one more thing, this operation, this flipping operation, we can perform this operation only once
at the max, once it is not necessary that we will do flip operation.
But if you want to do flip operation at Max, you can do only one time.
So given the string, my aim, my aim of flipping is basically to create a maximum number of buttons
and then you string to basically maximize one in the newly created string.
That is the ultimate aim.
Right, so I'm repeating myself, given a string string will contain a binary thing, so it will contain
obviously zeros and ones.
My aim is to maximize the number of points in the string and for maximizing the number of ones.
Answering the question is providing us option that you can flip and what values you can flip.
So all the values between left and right you can flip.
And how do we figure out the values of left and right?
That is your question.
So you need to figure out the values of left and right such that if you flip all the values from left
to right, the number of ones in the newly created string will be maximized.
Right.
So in this example, this is my by zero one zero.
And this is simple.
ELLENDER So when and when replace this.
So this thing will become one one zero, then one and two left is one, right.
Two.
So I will replace these two.
So it will become one zero zero in this case.
One, two, three.
So one, two, three means flip the entire string so it will become one zero one zero one, then two
to three.
So replace these two characters so it will become zero zero and one.
OK, so this is two and two.
So it means zero zero zero.
Right.
And this is two and three.
So that means these two characters.
So it becomes zero zero and one.
So in this and in this, we have two ones.
So number of once the count of onces two.
So my answer can be this one and my answer can be this one, because both of these are giving me equal
number of wins.
Right.
So these are the maximum number of wins in the new string.
Now, the question is, what should be done at this one or this one?
Now, it does give an indication that if you have more than one possible answer, more than one possible
combination of Ellender are giving you the maximum number of wins.
That is equal number of maximum ones.
Then you need to report your answer if the lexicographical is smallest.
So what do you mean by lexicographical smallest?
So we will compare.
This is one and this is an OK.
They are equal.
Now compare the value of.
Right.
So this is one and this is three.
So one is less than three.
So this will be my answer.
My answer will be one and one.
So that is the meaning of lexicographical smallest.
Now let's see this example.
So in this example, all the values are on alert, even in this case, what the value of and are I told
you at the max you can do this operation once, but this operation is optional.
If you want to do it, we can.
If you don't want to do it, then don't do it.
So in this case, we will not perform flip operation because all the values are already when and if
we are not flipping.
That means the value of left and right are not defined.
And if they are not defined, I will return ampitheater.
If left and right does not exist, then I will return empty array and if left cannot exist, then what
I will do so in Inari I will create an area of size two.
I will insert left, I will insert right, and I will return this area.
So that is the problem statement.
I hope you understood the question and now we need to think how we can solve this question.
So it's very simple.
It's actually the variation of Caden's algorithm.
So how could an algorithm will help us here?
Let me take one example.
OK, so let's take one example and let's try to understand how this will work.
So this is this is my string zero zero one one one zero.
I want to find out the value of left and right.
So by observation, I can tell that the value of left is one and the value of right is two.
So if we will flip these two, then what will happen?
The string will become one one one, one one and zero.
So this string is containing five ones.
So that will be our answer.
Right.
So these are the makes a number of ones that can be possible to what Caden's algorithm says, but we
will do so either replace zero by one and I will replace one by minus one night.
But we need to do we need to maximize the number of ones and how we can maximize number of ones by flipping
zero to one late.
So by flipping 021 one, I can maximize the number of ones.
So that means whenever we encounter zero, I will treat it as one.
And whenever we encounter one, I will treat it as minus one.
So I know this seems very weird, but this is the trick for solving this question.
Right.
And how district will help us see this is your string, right?
This is your input string.
So let's apply this.
Let's try to replace the zero means one one and one means minus one.
So this is minus one, minus one.
Minus one and zero minus one.
So this is your new string according to this formula, right?
According to this formula.
This is my new string.
I'll run Caden's algorithm, so what Caden's algorithm gives us, it gives us the maximum sum contiguous
Sabeti.
And what will be the maximum contiguous average this this will be the maximum contiguous average and
the sum is to date.
So what we need to do, we need to find out the maximum some contiguous.
Sabeti So this is the maximum savary and the sum is two.
So this will be my left and this will be my right.
And that is the right answer.
Right.
Let me take one more example.
Let's take this example, which is give given indication this one.
So let's convert this string on basis of this tricky part.
So replace zero with one and replace one with minus one.
So this will be your new string.
Right.
And what we will do, we will then condense algorithm on this to find out the maximum Sabeti size,
maximum symbolism.
So here we have two possibilities.
The maximum Subedi for this is one, and we have one more possibility.
So sum is one.
So we have two possibilities right here.
We have two possibilities.
So this will be the value of left and right, and this will be the value of left and right.
So that means this is index zero.
But in this case, we need to report our answer as indexing one.
So one common one can be our answer or this.
This is Tecoma three can be our answer.
Right.
So two answers are possible.
So when government means convert this into one one zero and three, three means convert it to zero one
and one night.
So two answers are possible.
And what we need to do, we need to report our answer is minimum, lexicographical minimum.
So I will report my answer is this one.
So.
Right.
What we need to do, very, very simple.
Whenever you encounter zero or replace it with one, whenever you encounter one, replace it with minus
one, then find out the maximum some Saberi, you will be able to find out the maximum sum.
Sabeti And the starting point of the maximum some somebody will be left and the ending point will be
are.
So that's how you will be able to solve this question.
Let me take one more example.
So let's say I have one when and then zero zero zero zero and then one and then again do right.
So according to the trick or Tulu one means this is minus one.
This is minus one.
This is when, when, when, when.
This is minus one.
And this is when applied Caden's algorithm.
So this will be the maximum sum.
Saberi and the sum is four.
So the starting point will be the left.
This is my left and the ending point will be my right.
So this is the value of left.
And this is the value of right.
So that's how you will be able to find out.
You will be able to solve this question.
So this is index zero one.
This is index to left is index two, three, four, five, and right this index six.
So you will report your answer as three, comma seven, because it is giving the question that you need
to report the answer by one indexing this.
Right.
So this is zero one two.
I read the index is two, but we need to add plus one when we will report our answer.
Similarly, the right values six, but we will add plus one when we will report our answer.
So that's how you can use them.
So I highly recommend that you try according this problem and if you are able to do it, then it's very
good.
Otherwise you can always watch this in our next video so that good guys, I will meet you in the next
one.
Thank you.