Maximize Active Section with Trade I | LeetCode 3499 - Python

[00:00:00]Hello everyone, I'm Paul and this is problem 3,499.

[00:00:05]Maximize active section with trade one.

[00:00:08]This is a medium problem and the key to solve it is observations. So let's start. We are given a binary string meaning a string with only zeros and ones. Ones are active sections and zeros are inactive sections. We can perform at most one of these operations and the job is to get the maximum number of active sections meaning once after this operation and the operation goes as follows. First we can convert a continuous block of ones that's surrounded by zeros to all zeros. For example here we have a one that's rounded by zeros. So we can convert this to zero. And then we can convert the continuous block of zeros that's rounded by ones to all ones. Let's say that we have a one to the left. Now we have a block with all zeros here that's rounded by ones. So we can convert all of these to ones. One, one, one, one. And here it says that we need to treat the string as if we had ones at both ends. So let's imagine that we have a one here and another one here. So where should we use the operation? Because here we have two blocks of ones that are surrounded by zeros. Let's say that we decide to use the operation here. First we transform this block of ones into all zeros. So we get something like this. Then we transform this block of zeros into all ones. And after doing this, the total number of ones without counting these two ends is one, two, three, four, five.

[00:01:43]If we decide to use the operation here instead, we can replace this with zero.

[00:01:48]And now this block of zeros is in between these two ones. So we can replace all of this with ones. And now the total number of ones is 1, two, three, four, five, six. Given that six is larger than five and we are looking for the maximum number of ones after the optimal operation the result here is six. Let's say for a moment that we don't have the operation available. What would be the result in this scenario?

[00:02:18]Well the number of ones right so in this case that would be two. Now given that we have the operation we can only use it in scenarios in which we have a block of ones surrounded by zeros. Why? Well, remember that this is the first step of the operation. In the opposite scenario with a block of zeros rounded by ones, we can't use it. We have to start with something like this. So here we have two choices. So we can say that the final result is the initial number of ones plus the maximum number of zeros surrounding some block of ones. Here we have three zeros surrounding this block.

[00:03:00]And here we have four zeros surrounding this block. The maximum between three and four is four. So we should use the operation here. After the operation, we transform all of these into ones. So the final result will be the initial number of ones plus the total number of zeros rounding some block of ones which in this case is four. 2 + 4 is equal to 6.

[00:03:27]The next question is how do we get the maximum number of zeros surrounding a block with ones? Well, for every candidate we have to look left and right which means that we are looking at blocks with zeros. So we can build an array where every value corresponds to the length of a continuous block of zeros. Here we have one and the length is one. So here we put one. The next block of zeros is right here. The length is two. So here we put two. The next block of zeros is here. The length is two. So here we put two. Now we can say that the best value that we've seen so far is initially zero. And we are iterating these blocks from index one.

[00:04:09]So here is the I pointer. And every time here we keep the maximum between what we already have and the current value plus the previous value. 2 + 1 is three which is greater than zero. So here we put three. And just to be clear, this means that here we have one zero. Here we have two zeros. 2 + 1 is equal to three.

[00:04:28]Which means that we have three zeros surrounding this block of ones. So the result up to this moment regarding the maximum number of zeros is three. Now we are here. So in best we keep the maximum between three and 2 + 2. So here we put four. And just to be clear this means that we have two zeros to the left, two zeros to the right regarding this block of ones and the sum is four. Given that four is larger than three, the new best is four. Now we move the I pointer and we are out of bounds. So the final result is the initial number of ones two plus the maximum number of zeros surrounding a block with ones four. 2 + 4 is equal to six. Time and space complexity for this will be big of n. So with this in mind, now let's go with the code. First we can say that n is the length of the string. The initial number of ones is zero. And we need an array for sections of zeros. This is empty initially. And now we can say that i is at index zero. And while i is strictly smaller than n, we are inbound. So we check if the current character is either one or zero. If it's a zero, we need to count the number of zeros in this block.

[00:05:46]So we can say that sh is equal to i and while sh is smaller than n meaning we are inbounds and the character at sh is equal to the character at i we move sh after this while loop we can say sections do append the number of zeros which is given by the right bound minus the left bound + one. So here we use sh minus i and down here we can update i to whatever we have sh else this means that the current character is a one. So we can say once plus equal one and we move the i pointer one step forward. After this while loop down here we can check if the length of sections is strictly smaller than two. In this scenario, there's no scenario with a block of ones surrounded by zero. So we can just return the number of ones. If we are down here, the number of sections is greater or equal to two in which case we can get best. Remember that this is the maximum number of zeros that we can get surrounding a block of ones. So now we can say for in range we go from one to the length of sections and down here every time the best is the maximum between what we already have and the current value section side plus the previous value section I minus one. We are checking every pair of consecutive sections of zeros. After this we can return the number of ones plus best. So, let's submit this and see if it works.

[00:07:28]As you can see, this works and it's very efficient. So, if you found this useful, please drop a like, subscribe, and see you in the next one. Bye-bye.