Recuento mínimo de 0 que se seleccionará de modo que todos los 1 sean adyacentes a ellos

Dada una string binaria str de tamaño N cuyos caracteres son ‘1’ o ‘0’ . La tarea es seleccionar el número mínimo de 0 de modo que se seleccione al menos un vecino por cada ‘1’ . Imprime el conteo de los 0 ‘s seleccionados.

Ejemplos: 

Entrada: str = “1001”
Salida: 2
Explicación: Los ‘0’ pueden seleccionarse del índice 1 y el índice 2. Como resultado, cada ‘1’ tiene al menos un vecino presente entre los ‘0’ seleccionados.

Entrada: str = “01010”
Salida : 1
Explicación: Se puede seleccionar ‘0’ en el índice 2. Como resultado, se selecciona un vecino para ambos ‘1’.

Entrada: str = “111”
Salida: -1
Explicación: No hay ‘0’ en la string dada. Entonces no puede haber ningún vecino de ‘1’ que sea ‘0’.

Entrada: str = “110”
Salida: -1
Explicación: No hay ‘0’ como vecino para ‘1’ en la primera posición.

Enfoque: La solución se basa en el enfoque codicioso . Siga los pasos a continuación para obtener la solución.

• Comience a iterar la string desde el principio.
• Para cada ‘1’ Si es posible, se selecciona un ‘0’ de su vecindad.
• Ahora, si hay un ‘0’ antes y después del ‘1’ actual , seleccione siempre el vecino al lado del ‘1’ actual (porque puede haber más ‘1’ después de este y al hacerlo permitirá seleccionar el número mínimo de vecinos).

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count
// minimum number of buckets
int minimumBuckets(string str)
{
    int bucketcount = 0;
    int N = str.size();
 
    // Loop to count minimum buckets
    for (int i = 0; i < N;) {
        if (str[i] == '1') {
             
            // If bucket can be put,
            // no need of next two indices,
            // so shift to i+3
            if (i + 1 < N &&
                str[i + 1] == '0') {
                bucketcount++;
                i += 3;
                continue;
            }
            if (i - 1 >= 0 &&
                str[i - 1] == '0') {
                bucketcount++;
                i++;
                continue;
            }
            return -1;
        }
        i++;
    }
    return bucketcount;
}
 
// Driver code
int main()
{
    string str = "1001";
    cout << minimumBuckets(str)<<endl;
   
    string str1 = "1010";
    cout << minimumBuckets(str1);
    return 0;
}

// Java code to implement the above approach
class GFG {
 
    // Function to count
    // minimum number of buckets
    static int minimumBuckets(String str) {
        int bucketcount = 0;
        int N = str.length();
 
        // Loop to count minimum buckets
        for (int i = 0; i < N;) {
            if (str.charAt(i) == '1') {
 
                // If bucket can be put,
                // no need of next two indices,
                // so shift to i+3
                if (i + 1 < N && str.charAt(i + 1) == '0') {
                    bucketcount++;
                    i += 3;
                    continue;
                }
                if (i - 1 >= 0 && str.charAt(i - 1) == '0') {
                    bucketcount++;
                    i++;
                    continue;
                }
                return -1;
            }
            i++;
        }
        return bucketcount;
    }
 
    // Driver code
    public static void main(String args[]) {
        String str = "1001";
        System.out.println(minimumBuckets(str));
 
        String str1 = "1010";
        System.out.println(minimumBuckets(str1));
    }
}
 
// This code is contributed by Saurabh Jaiswal

# python code to implement the above approach
 
# Function to count
# minimum number of buckets
def minimumBuckets(str):
 
    bucketcount = 0
    N = len(str)
 
    # Loop to count minimum buckets
    i = 0
    while(i < N):
        if (str[i] == '1'):
 
            # If bucket can be put,
            # no need of next two indices,
            # so shift to i+3
            if (i + 1 < N and str[i + 1] == '0'):
                bucketcount += 1
                i += 3
                continue
 
            if (i - 1 >= 0 and str[i - 1] == '0'):
                bucketcount += 1
                i += 1
                continue
 
            return -1
 
        i += 1
 
    return bucketcount
 
# Driver code
if __name__ == "__main__":
 
    str = "1001"
    print(minimumBuckets(str))
 
    str1 = "1010"
    print(minimumBuckets(str1))
 
    # This code is contributed by rakeshsahni

// C# code to implement the above approach
using System;
class GFG {
 
    // Function to count
    // minimum number of buckets
    static int minimumBuckets(string str)
    {
        int bucketcount = 0;
        int N = str.Length;
 
        // Loop to count minimum buckets
        for (int i = 0; i < N;) {
            if (str[i] == '1') {
 
                // If bucket can be put,
                // no need of next two indices,
                // so shift to i+3
                if (i + 1 < N && str[i + 1] == '0') {
                    bucketcount++;
                    i += 3;
                    continue;
                }
                if (i - 1 >= 0 && str[i - 1] == '0') {
                    bucketcount++;
                    i++;
                    continue;
                }
                return -1;
            }
            i++;
        }
        return bucketcount;
    }
 
    // Driver code
    public static void Main()
    {
        string str = "1001";
        Console.WriteLine(minimumBuckets(str));
 
        string str1 = "1010";
        Console.WriteLine(minimumBuckets(str1));
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript code for the above approach
 
        // Function to count
        // minimum number of buckets
        function minimumBuckets(str) {
            let bucketcount = 0;
            let N = str.length;
 
            // Loop to count minimum buckets
            for (let i = 0; i < N;) {
                if (str[i] == '1') {
 
                    // If bucket can be put,
                    // no need of next two indices,
                    // so shift to i+3
                    if (i + 1 < N &&
                        str[i + 1] == '0') {
                        bucketcount++;
                        i += 3;
                        continue;
                    }
                    if (i - 1 >= 0 &&
                        str[i - 1] == '0') {
                        bucketcount++;
                        i++;
                        continue;
                    }
                    return -1;
                }
                i++;
            }
            return bucketcount;
        }
 
        // Driver code
        let str = "1001";
        document.write(minimumBuckets(str) + '<br>');
 
        let str1 = "1010";
        document.write(minimumBuckets(str1) + '<br>');
 
  // This code is contributed by Potta Lokesh
    </script>

2
1

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