Flip all zeros to ones

Given a string of bits and a number k. In one flip, you can toggle k consecutive characters, how many flips are required to change the entire string to all ones. For example

Input String: 0000110000
k: 3
OUTPUT: 4

Following are the four flips:

FLIP-1: 1110110000
FLIP-2: 1110110111
FLIP-3: 1111000111
FLIP-4: 1111111111

If it is not possible to set all bits in the string then return -1. For example:

Input String: 01010101
k: 3
OUTPUT: -1

Solution: Brute force
If there are n bits, then total number of places that can be flipped are n-k+1, each position can either be flipped or not. This way, the total number of possible combinations of flips are 2^n-k+1. In all these possible combinations we will check if the string is valid or not (if string has zeros it is invalid combination). If the combinations of flips are valid then we check them against each other and finally return the minimum of all of them.
Solution: Greedy Approach
The following greedy approach in this case works fine:

At each point convert the left-most ‘0’ to ‘1’

So if the Input string is 0001000000001110 and k=4
The first zero is found at the (red) position, 0001000000001110, we flip the next k(4) bits. The array will become, 1110000000001110. Now we will flip the next zero-bit (show in red), 1110000000001110. Now, we will toggle the next 4 bits starting from left-most zero (shown in red). The array will become

1111111000001110

We will again find the leftmost zero and toggle next k bits. The array will then become

1111111111101110

Again we will find the leftmost zero (1111111111101110) and toggle next k bits. The array will then become.

1111111111110000

Now the left-most zero is found at position, shown in red

1111111111110000

Toggling the 4 bits starting from left-most zero bit, we get get the all-set array. Hence the total number of flips required are 5.
Code:

For a change, I am putting the code in java. But the logic can very well be translated to C++

public class First
{
   public static int countFlips(char[] str, int k)
   {
      int flips = 0, i=0;
      int n = str.length-k;
      for(; i<=n; i++)
      {
         if(str[i] == '0')
         {
            // FLIP next k bits
            for(int j=0; j<k; j++)
               str[j+i] = (str[j+i] == '0') ? '1':'0';
            flips++;
         }
      }
      for(; i<str.length; i++)
         if(str[i] == '0')
            return -1;
      return flips;
   }
   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      String str = sc.next();
      int k = sc.nextInt();
      int flips = countFlips(str.toCharArray(), k);
      if(flips == -1)
         System.out.println("Not possible to convert string");
      else
         System.out.println("String can be changed in "+ flips + " flips");
   }
}