I have a string of 0's and 1's

Now I want to change 0 to 1 only if adjacent elements for that 0 are not 1'string. Find the maximum ones possible after doing this operation.

Example:

110011000001 is the input string

Option 1:

I can change position 8 and position 10 from 0 to 1 to make the string: 110011010101, here there are 7 ones

Option 2:

Another way is to change position 9 from 0 to 1, to make the string: 110011001001, here there are 6 ones.

So the maximum between 6 and 7 is 7. So the result is 7.

Here is my code, I am able to find only one possible way here:

int process(String s) {
    char[] ch = s.toCharArray();
    int n = ch.length;
    for(int i=1; i<n-1; i  ) {
        char e = ch[i];
        if(e == '0' && ch[i-1] != '1' && ch[i 1] != '1') {
            ch[i] = '1';
        }
    }
    int count = 0;
    for(char c : ch) {
        if(c == '1') count  ;
    }   
    return count;
}

How to get the maximum possible ones here.

CodePudding user response：

• Count all existing ones as they are going to be a part of the answer.

• To convert 0 to 1, count all zeroes between two ones.

  • If string is 100001, you have total 4 zeroes in between. Here let us leave boundary zeroes as we can't change them as they are adjacent to 1. So, now we are left with 2 zeroes in the middle out of which we can place only in 1 of them.

  • So count is just ceil(all valid zeroes / 2).

    • If you have a string like 00001, here you can place 2 ones excluding that boundary 0 adjacent to 1. So, count is ceil(3/2) which is 2. Your string would look like 10101.

• Final answer is just step 1 step 2.

CodePudding user response：

1. Notice that if the 0's are surrounded by 1's, you only need 2n 1 adjacent 0's in order to add n 1's. In order to add one 1, you need at least three 0's: 2*1 1=3. In order to add two 1's, you need at least five 0's: 2*2 1=5. Since the number of 0's can be described as, Z >= 2n 1, we can instead solve for n. We get n <= (Z - 1) / 2. Thus, when surrounded by 1's, each group of 0's can fit n=floor((Z-1)/2); we floor the value since we can't add half of a 1.
2. For groups of 0's only bounded by a 1 on a single side, we notice that we need at least 2n 0's in order to add n 1's. Again, we rearrange the equation Z >= 2n in order to get n <= Z / 2. Thus, for groups bounded by a single 1, n=floor(Z/2).
3. For our last case, with a string of all 0's, we see that Z >= 2n - 1. So, n <= (Z 1) / 2, or for our purposes floor((Z 1)/2).

Least common will be category 3. This will only happen if there are no 1's. If this is the case, you cannot have anything from category 1 or 2 -- so check this category first.
Second most common will be category 2. This happens when the beginning OR end of the string is a 0, but there are 1's elsewhere. Check this category second because you can fit more 1's with it than with the formula for the first case. You will have to keep track of the places you've already checked before moving on to using case 1 by using a substring of the original.
Most cases will land in category 1, since (in a random combination of 1's and 0's) most groups of 0's will be surrounded by 1's.

Your answer only checks the first case. Using these three cases together will give you the number of 1's that you can add to the string. Add this to the number of 1's you had originally and you'll have your answer.

Edited for clarity.