Recuento de 0 que se invertirán para hacer que dos 1 adyacentes estén separados por al menos K 0

Dada una string binaria s y un número K, la tarea es encontrar el número máximo de 0 que se pueden reemplazar por 1 de manera que dos 1 adyacentes estén separados por al menos K 0 entre ellos. 
Ejemplos: 

Entrada: K = 2, s = “000000” 
Salida: 2 
Explicación:
Cambie los 0 en la posición 0 y 3. Luego, la string final será “100100” de modo que cada 1 esté separado por al menos 2 0 .

Entrada: K = 1, s = «01001000100000» 
Salida: 3 
Explicación:
Cambie los 0 en las posiciones 6, 10 y 12. Luego, la string final será «01001010101010», de modo que cada 1 esté separado por al menos 1 0 .

Acercarse: 

1. Inserte todos los caracteres de la string dada en una array (digamos arr[]) .
2. Recorra la array arr[] y convierta todos los 0 en -1 que se encuentran en <= K lugares cerca de un 1 ya existente . Esta operación da todas las posiciones posibles de la string donde se puede insertar 1 .
3. Inicializar una variable de conteo a 0.
4. Recorre la array arr[] desde la izquierda hasta el final. Tan pronto como se encuentre el primer 0, reemplácelo con 1 y aumente el valor de conteo.
5. Convierta todos los 0 en -1 que se encuentran en <= K lugares cerca del 1 recién convertido.
6. Siga recorriendo la array hasta el final y cada vez que encuentre un 0, repita los pasos 4 y 5 .

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// count of 0s to be flipped
int count(int k, string s)
{
    int ar[s.length()];
    int end = 0;
     
    // Loop traversal to mark K
    // adjacent positions to the right
    // of already existing 1s.
    for(int i = 0; i < s.length(); i++)
    {
       if (s[i] == '1')
       {
           for(int j = i;
                   j < s.length() &&
                   j <= i + k; j++)
           {
              ar[j] = -1;
              end = j;
           }
           i = end;
       }
    }
    end = 0;
     
    // Loop traversal to mark K
    // adjacent positions to the left
    // of already existing 1s.
    for(int i = s.length() - 1;
            i >= 0; i--)
    {
       if (s[i] == '1')
       {
           for(int j = i;
                   j >= 0 &&
                   j >= i - k; j--)
           {
              ar[j] = -1;
              end = j;
           }
           i = end;
       }
    }
     
    int ans = 0;
    end = 0;
     
    // Loop to count the maximum
    // number of 0s that will be
    // replaced by 1s
    for(int j = 0;
            j < s.length(); j++)
    {
       if (ar[j] == 0)
       {
           ans++;
           for(int g = j;
                   g <= j + k &&
                   g < s.length(); g++)
           {
              ar[g] = -1;
              end = g;
           }
           j = end - 1;
       }
    }
    return ans;
}
 
// Driver code
int main()
{
    int K = 2;
    string s = "000000";
 
    cout << count(K, s) << endl;
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

// Java program for the above problem
import java.util.Scanner;
 
// Driver Code
public class Check {
 
    // Function to find the
    // count of 0s to be flipped
    public static int count(int k, String s)
    {
 
        int ar[] = new int[s.length()];
        int end = 0;
 
        // Loop traversal to mark K
        // adjacent positions to the right
        // of already existing 1s.
        for (int i = 0;
             i < s.length(); i++) {
 
            if (s.charAt(i) == '1') {
 
                for (int j = i;
                     j < s.length()
                     && j <= i + k;
                     j++) {
 
                    ar[j] = -1;
                    end = j;
                }
                i = end;
            }
        }
 
        end = 0;
 
        // Loop traversal to mark K
        // adjacent positions to the left
        // of already existing 1s.
        for (int i = s.length() - 1;
             i >= 0; i--) {
 
            if (s.charAt(i) == '1') {
                for (int j = i;
                     j >= 0 && j >= i - k;
                     j--) {
 
                    ar[j] = -1;
                    end = j;
                }
 
                i = end;
            }
        }
 
        int ans = 0;
        end = 0;
 
        // Loop to count the maximum
        // number of 0s that will be
        // replaced by 1s
        for (int j = 0;
             j < s.length(); j++) {
 
            if (ar[j] == 0) {
 
                ans++;
                for (int g = j;
                     g <= j + k
                     && g < s.length();
                     g++) {
 
                    ar[g] = -1;
                    end = g;
                }
 
                j = end - 1;
            }
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int K = 2;
        String s = "000000";
 
        System.out.println(count(K, s));
    }
}

# Python3 program for the above problem
 
# Function to find the 
# count of 0s to be flipped
def count(k, s):
     
    ar = [0] * len(s)
    end = 0
 
    # Loop traversal to mark K 
    # adjacent positions to the right 
    # of already existing 1s.
    for i in range(len(s)):
        if s[i] == '1':
             
            for j in range(i, len(s)):
                if (j <= i + k):
                    ar[j] = -1
                    end = j
                     
            i = end
             
    end = 0
 
    # Loop traversal to mark K 
    # adjacent positions to the left 
    # of already existing 1s.
    for i in range(len(s) - 1, -1, -1):
        if (s[i] == '1'):
             
            for j in range(i, -1, -1):
                if (j >= i - k):
                    ar[j] = -1
                    end = j
                     
            i = end
             
    ans = 0
    end = 0
 
    # Loop to count the maximum 
    # number of 0s that will be 
    # replaced by 1s
    for j in range(len(s)):
        if (ar[j] == 0):
            ans += 1
             
            for g in range(j, len(s)):
                if (g <= j + k):
                    ar[g] = -1
                    end = g
                     
            j = end - 1
             
    return ans
 
# Driver code
K = 2
s = "000000"
 
print(count(K, s))
 
# This code is contributed by avanitrachhadiya2155

// C# program for the above problem
using System;
 
class GFG{
 
// Function to find the
// count of 0s to be flipped
public static int count(int k, String s)
{
 
    int []ar = new int[s.Length];
    int end = 0;
 
    // Loop traversal to mark K
    // adjacent positions to the right
    // of already existing 1s.
    for(int i = 0; i < s.Length; i++)
    {
       if (s[i] == '1')
       {
           for(int j = i;
                   j < s.Length &&
                   j <= i + k; j++)
           {
              ar[j] = -1;
              end = j;
           }
           i = end;
       }
    }
    end = 0;
     
    // Loop traversal to mark K
    // adjacent positions to the left
    // of already existing 1s.
    for(int i = s.Length - 1; i >= 0; i--)
    {
       if (s[i] == '1')
       {
           for(int j = i;
                   j >= 0 &&
                   j >= i - k; j--)
           {
              ar[j] = -1;
              end = j;
           }
           i = end;
       }
    }
     
    int ans = 0;
    end = 0;
 
    // Loop to count the maximum
    // number of 0s that will be
    // replaced by 1s
    for(int j = 0; j < s.Length; j++)
    {
       if (ar[j] == 0)
       {
           ans++;
           for(int g = j;
                   g <= j + k &&
                   g < s.Length; g++)
           {
              ar[g] = -1;
              end = g;
           }
           j = end - 1;
       }
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int K = 2;
    String s = "000000";
 
    Console.WriteLine(count(K, s));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript program for the above problem
 
// Function to find the
// count of 0s to be flipped
function count(k, s)
{
    var ar = Array(s.length).fill(0);
    var end = 0;
     
    var i,j;
    // Loop traversal to mark K
    // adjacent positions to the right
    // of already existing 1s.
    for(i = 0; i < s.length; i++)
    {
       if (s[i] == '1')
       {
           for(j = i; j < s.length &&
               j <= i + k; j++)
           {
              ar[j] = -1;
              end = j;
           }
           i = end;
       }
    }
    end = 0;
     
    // Loop traversal to mark K
    // adjacent positions to the left
    // of already existing 1s.
    for(i = s.length - 1; i >= 0; i--)
    {
       if (s[i] == '1')
       {
           for(j = i; j >= 0 &&
               j >= i - k; j--)
           {
              ar[j] = -1;
              end = j;
           }
           i = end;
       }
    }
     
    var ans = 0;
    end = 0;
     
    // Loop to count the maximum
    // number of 0s that will be
    // replaced by 1s
    var g;
    for(j = 0;j < s.length; j++)
    {
       if (ar[j] == 0)
       {
           ans++;
           for(g = j; g <= j + k &&
               g < s.length; g++)
           {
              ar[g] = -1;
              end = g;
           }
           j = end - 1;
       }
    }
    return ans;
}
 
// Driver code
    var K = 2;
    var s = "000000";
 
    document.write(count(K, s));
 
</script>

2

Complejidad temporal: O(N * K) 
Espacio auxiliar: O(1)