Flip bits in binary string and avoid 10 pattern

I have a binary string with bits 0 and 1 of length n. I want to flip the bits that is turn 0 to 1 and 1 to 0 in such a way that there is no substring with 10 pattern. Find the minimum number of flips needed.

Example: Input = 10110 Output = 2 Explanation: flip bits at index 0 and 4 so string becomes 00111, here there is no substring with pattern 10

Constraints: length of string n is 1 to 3*10^5

Here is my code:

static int solve(String s) {
  int n = s.length();
  int flips = 0;
  char[] ar = s.toCharArray();
  for(int i=0; i<n-1; i++) {
      if(ar[i] == '1' && ar[i+1] == '0') {
      flips++;
      ar[i+1]='1'
   }
  }
  return flips;
}

Here I am checking for pattern 10, if found I am changing it to 11. But this code approach is not correct, as I need to find the minimum, so what is the correct approach to solve this problem?

Solution

This can be solved with dynamic programming.

For each index, there are two choices: make the bit 0 or 1. Instead of trying an exponential number of possibilities, we can simply track the minimum number of operations for both choices that results in a valid prefix of the binary string up to that index. Note that the choice of bit at each index depends only on the previous bit, so we have a constant time transition (and overall linear solution).

Let minOps[i][b] denote the minimum number of operations to make the prefix of the binary string up to index i valid and end in the bit b.

If the current bit is to be 0, the previous bit must also be 0.

Thus, minOps[i][0] = minOps[i - 1][0] + (1 if current bit is not 0).

For setting the current bit to 1, the previous bit could be anything (but the previous bits must be valid) as appending a 1 can never create a 10 substring in a string that did not previously contain it, so

minOps[i][1] = min(minOps[i - 1][0], minOps[i - 1][1]) + (1 if current bit is not 1).

Finally, the answer is the minimum of the two states at the last index as the last bit could be set to either 0 or 1.

We do not need to store the entire minOps array; it suffices to maintain only the previous and current state as shown in the solution below.

var minOps = new int[2];
for (char c : s.toCharArray())
    minOps = new int[]{minOps[0] + (c != '0' ? 1 : 0), 
                Math.min(minOps[0], minOps[1]) + (c != '1' ? 1 : 0)};
return Math.min(minOps[0], minOps[1]);