Cambios de bits mínimos de modo que cada K bits consecutivos contengan al menos un bit establecido

Dada una string binaria S y un entero K , la tarea es encontrar el número mínimo de vueltas necesarias para que cada substring de longitud K contenga al menos un ‘1’ .
Ejemplos: 
 

Entrada: S = “10000001” K = 2 
Salida: 3 
Explicación: 
Solo necesitamos 3 cambios en la string S (en las posiciones 2, 4 y 6) para que la string contenga al menos un ‘1’ en cada substring de longitud 2.
Entrada: S = “000000” K = 3 
Salida: 2 
Explicación: 
Necesitamos solo 3 cambios en la string S (en las posiciones 2 y 5) para que la string contenga al menos un ‘1’ en cada substring de longitud 3.
Entrada: S = “111010111” K = 2 
Salida: 0 
 

Enfoque ingenuo: 
para resolver el problema, el enfoque más simple es iterar para cada substring de longitud K y encontrar la cantidad mínima de vueltas requeridas para satisfacer la condición dada. 
Complejidad de tiempo: O(N * K)
Enfoque eficiente: 
La idea es utilizar el enfoque de ventana deslizante . 
 

• Establezca un tamaño de ventana de K .
• Almacena el índice de aparición anterior de 1.
• Si el bit actual no está configurado y la diferencia entre el i ^-ésimo bit actual y el bit configurado anterior excede K , configure el bit actual y almacene el índice actual como el del bit configurado anterior y continúe.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count min flips
int CountMinFlips(string s, int n,
                  int k)
{
 
    // To store the count of minimum
    // flip required
    int cnt = 0;
 
    // To store the position of last '1'
    int prev = -1;
 
    for (int i = 0; i < k; i++) {
 
        // Track last position of '1'
        // in current window of size k
        if (s[i] == '1') {
            prev = i;
        }
    }
 
    // If no '1' is present in the current
    // window of size K
    if (prev == -1) {
        cnt++;
 
        // Set last index of window '1'
        s[k - 1] = '1';
 
        // Track previous '1'
        prev = k - 1;
    }
 
    // Traverse the given string
    for (int i = k; i < n; i++) {
 
        // If the current bit is not set,
        // then the condition for flipping
        // the current bit
        if (s[i] != '1') {
            if (prev <= (i - k)) {
 
                // Set i'th index to '1'
                s[i] = '1';
 
                // Track previous one
                prev = i;
 
                // Increment count
                cnt++;
            }
        }
 
        // Else update the prev set bit
        // position to current position
        else {
            prev = i;
        }
    }
 
    // Return the final count
    return (cnt);
}
 
// Driver Code
int main()
{
    // Given binary string
    string str = "10000001";
 
    // Size of given string str
    int n = str.size();
 
    // Window size
    int k = 2;
 
    // Function Call
    cout << CountMinFlips(str, n, k)
         << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count min flips
static int CountMinFlips(char []s, int n,
                                   int k)
{
     
    // To store the count of minimum
    // flip required
    int cnt = 0;
 
    // To store the position of last '1'
    int prev = -1;
 
    for(int i = 0; i < k; i++)
    {
        
       // Track last position of '1'
       // in current window of size k
       if (s[i] == '1')
       {
           prev = i;
       }
    }
 
    // If no '1' is present in the current
    // window of size K
    if (prev == -1)
    {
        cnt++;
 
        // Set last index of window '1'
        s[k - 1] = '1';
 
        // Track previous '1'
        prev = k - 1;
    }
 
    // Traverse the given String
    for(int i = k; i < n; i++)
    {
        
       // If the current bit is not set,
       // then the condition for flipping
       // the current bit
       if (s[i] != '1')
       {
           if (prev <= (i - k))
           {
                
               // Set i'th index to '1'
               s[i] = '1';
                
               // Track previous one
               prev = i;
                
               // Increment count
               cnt++;
           }
       }
        
       // Else update the prev set bit
       // position to current position
       else
       {
           prev = i;
       }
    }
     
    // Return the final count
    return (cnt);
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given binary String
    String str = "10000001";
 
    // Size of given String str
    int n = str.length();
 
    // Window size
    int k = 2;
 
    // Function Call
    System.out.print(CountMinFlips(
                     str.toCharArray(), n, k) + "\n");
}
}
 
// This code is contributed by Rohit_ranjan

# Python3 code to count minimum no.
# of flips required such that
# every substring of length K
# contain at least one '1'.
 
# Function to count min flips
def CountMinFlips(s, n, k):
    cnt = 0
    prev = -1
    for i in range(0, k):
        # Track last position of '1'
        # in current window of size k
        if(s[i]=='1'):
            prev = i;
             
    # means no '1' is present
    if(prev == -1):
        cnt += 1
        # track previous '1'
        prev = k-1;
         
     
    for i in range(k, n):
        if(s[i] != '1'):
            if( prev <= (i-k) ):
                 
                # track previous one
                prev = i;
                 
                # increment count
                cnt += 1
        else:
            prev = i
     
    return(cnt);
 
# Driver code
s = "10000001"
n = len(s)
k = 2
print(CountMinFlips(s, n, k))

// C# program for the above approach
using System;
class GFG{
 
// Function to count min flips
static int CountMinFlips(char []s, int n,
                                   int k)
{
     
    // To store the count of minimum
    // flip required
    int cnt = 0;
 
    // To store the position of last '1'
    int prev = -1;
 
    for(int i = 0; i < k; i++)
    {
         
        // Track last position of '1'
        // in current window of size k
        if (s[i] == '1')
        {
            prev = i;
        }
    }
 
    // If no '1' is present in the current
    // window of size K
    if (prev == -1)
    {
        cnt++;
 
        // Set last index of window '1'
        s[k - 1] = '1';
 
        // Track previous '1'
        prev = k - 1;
    }
 
    // Traverse the given String
    for(int i = k; i < n; i++)
    {
         
        // If the current bit is not set,
        // then the condition for flipping
        // the current bit
        if (s[i] != '1')
        {
            if (prev <= (i - k))
            {
                     
                // Set i'th index to '1'
                s[i] = '1';
                     
                // Track previous one
                prev = i;
                     
                // Increment count
                cnt++;
            }
        }
             
        // Else update the prev set bit
        // position to current position
        else
        {
            prev = i;
        }
    }
     
    // Return the readonly count
    return (cnt);
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Given binary String
    String str = "10000001";
 
    // Size of given String str
    int n = str.Length;
 
    // Window size
    int k = 2;
 
    // Function Call
    Console.Write(CountMinFlips(
                  str.ToCharArray(), n, k) + "\n");
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// javascript program for the above approach
 
// Function to count min flips
function CountMinFlips(s , n,k)
{
     
    // To store the count of minimum
    // flip required
    var cnt = 0;
 
    // To store the position of last '1'
    var prev = -1;
 
    for(i = 0; i < k; i++)
    {
        
       // Track last position of '1'
       // in current window of size k
       if (s[i] == '1')
       {
           prev = i;
       }
    }
 
    // If no '1' is present in the current
    // window of size K
    if (prev == -1)
    {
        cnt++;
 
        // Set last index of window '1'
        s[k - 1] = '1';
 
        // Track previous '1'
        prev = k - 1;
    }
 
    // Traverse the given String
    for(i = k; i < n; i++)
    {
        
       // If the current bit is not set,
       // then the condition for flipping
       // the current bit
       if (s[i] != '1')
       {
           if (prev <= (i - k))
           {
                
               // Set i'th index to '1'
               s[i] = '1';
                
               // Track previous one
               prev = i;
                
               // Increment count
               cnt++;
           }
       }
        
       // Else update the prev set bit
       // position to current position
       else
       {
           prev = i;
       }
    }
     
    // Return the final count
    return (cnt);
}
 
// Driver Code
 
 
    // Given binary String
    var str = "10000001";
 
    // Size of given String str
    var n = str.length;
 
    // Window size
    var k = 2;
 
    // Function Call
    document.write(CountMinFlips(
                     str, n, k) );
 
 
// This code contributed by shikhasingrajput
 
</script>

3

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