Maximice los subarreglos de 0 de longitud X en una string binaria dada después de voltear como máximo un ‘1’

Dada una string binaria str de longitud N y un entero positivo X , la tarea es maximizar el recuento de subarreglos de longitud X que consisten en solo 0 cambiando como máximo un 1 . Se considerará un bit en un solo subarreglo.
Ejemplo:

Entrada: str = 0010001″, X = 2
Salida: 3
Explicación: Cambia str[2] de 1 a 0, -> str = “0000001” -> Ahora cuenta los subarreglos de longitud X de 0 = 3 
Al voltear el índice 6 también dar cuenta resultante como 3.

Entrada: str = “00100”, X = 2
Salida: 2
Explicación: Cambiar str[2] de 1 a 0 no cambiará el grupo máximo de 0. Permanecerá igual que 2 solamente.

 

Enfoque: Para calcular el grupo máximo de ceros que contienen X ceros, siga los pasos a continuación:

  • Encuentra el número de grupos de ceros que contienen X ceros continuos.
  • Iterar sobre la string dada y al mismo tiempo mantener el conteo de ceros a la izquierda y ceros a la derecha si aparece ‘1’ durante la iteración.
  • Ahora verifique si volteamos el ‘1’ actual, afectará el grupo de ceros o no, si luego incrementará el grupo en 1 y lo devolverá, de lo contrario, continúe con la iteración y realice los pasos anteriores una y otra vez.
  • Devuelve el número de grupos.

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

C++

// C++ program of finding
// the maximum group of zeroes
// in a binary string after
// flipping at most one '1'
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// number of groups of X
// consecutive Zeroes
int maxGroupOfZeroes(string str, int X)
{
  int n = str.size();
 
  // Number of groups before flipping '1'
  int groups = 0;
 
  // Iterating over the string
  int i = 0;
  while (i < n) {
 
    // It will keep the track
    // of consecutive zeroes
    int zero = 0;
    while (i < n && str[i] == '0') {
      zero++;
      i++;
    }
    i++;
 
    // It will break those
    // consecutive zeroes into groups
    groups += (zero / X);
  }
 
  // Left variable will count
  // the consecutive zeroes
  // on the left side of '1'
  int left = 0;
 
  // Right variable will count
  // the consecutive zeroes
  // on the right size of '1'
  int right = 0;
 
  // Iterating str from 0 index
  i = 0;
  while (i < n) {
 
    char ch = str[i];
 
    // If it is '0' keep
    // incrementing left zeroes
    if (ch == '0') {
      left++;
      i++;
    }
    // Else increment
    // right zeroes while
    // character is '0'
    else {
 
      int j = i;
      i++;
      while (i < n && str[i] != '1') {
        i++;
        right++;
      }
 
      int contribute = (left + right + 1) / X;
      int without = ((left / X) + (right / X));
 
      // Checking after flipping
      // current '1' will
      // it affect the groups or not
      if (without != contribute) {
        return ++groups;
      }
 
      // If it doesn't affect
      // then right zeroes
      // will become left zeroes
      // and for right
      // zeroes we will have
      // to count it again
      left = right;
      right = 0;
    }
  }
 
  // Return number of groups
  return groups;
}
 
// Driver Code
int main()
{
  string str = "0010001";
  int X = 2;
  int max_groups = maxGroupOfZeroes(str, X);
  cout << (max_groups);
 
  return 0;
}
 
// This code is contributed by rakeshsahni

Java

// Java program of finding
// the maximum group of zeroes
// in a binary string after
// flipping at most one '1'
 
import java.util.*;
 
class GFG {
 
    // Function to find the maximum
    // number of groups of X
    // consecutive Zeroes
    public static int maxGroupOfZeroes(
        String str, int X)
    {
        int n = str.length();
 
        // Number of groups before flipping '1'
        int groups = 0;
 
        // Iterating over the string
        int i = 0;
        while (i < n) {
 
            // It will keep the track
            // of consecutive zeroes
            int zero = 0;
            while (i < n
                   && str.charAt(i) == '0') {
                zero++;
                i++;
            }
            i++;
 
            // It will break those
            // consecutive zeroes into groups
            groups += (zero / X);
        }
 
        // Left variable will count
        // the consecutive zeroes
        // on the left side of '1'
        int left = 0;
 
        // Right variable will count
        // the consecutive zeroes
        // on the right size of '1'
        int right = 0;
 
        // Iterating str from 0 index
        i = 0;
        while (i < n) {
 
            char ch = str.charAt(i);
 
            // If it is '0' keep
            // incrementing left zeroes
            if (ch == '0') {
                left++;
                i++;
            }
            // Else increment
            // right zeroes while
            // character is '0'
            else {
 
                int j = i;
                i++;
                while (i < n
                       && str.charAt(i) != '1') {
                    i++;
                    right++;
                }
 
                int contribute
                    = (left + right + 1) / X;
                int without
                    = ((left / X) + (right / X));
 
                // Checking after flipping
                // current '1' will
                // it affect the groups or not
                if (without != contribute) {
                    return ++groups;
                }
 
                // If it doesn't affect
                // then right zeroes
                // will become left zeroes
                // and for right
                // zeroes we will have
                // to count it again
                left = right;
                right = 0;
            }
        }
 
        // Return number of groups
        return groups;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String str = "0010001";
        int X = 2;
        int max_groups
            = maxGroupOfZeroes(str, X);
        System.out.println(max_groups);
    }
}

Python

# Python program of finding
# the maximum group of zeroes
# in a binary string after
# flipping at most one '1'
 
# Function to find the maximum
# number of groups of X
# consecutive Zeroes
def maxGroupOfZeroes(str, X):
 
    n = len(str)
 
    # Number of groups before flipping '1'
    groups = 0
 
    # Iterating over the string
    i = 0
    while (i < n):
 
        # It will keep the track
        # of consecutive zeroes
        zero = 0
        while (i < n and str[i] == '0'):
            zero += 1
            i += 1
 
        i += 1
 
        # It will break those
        # consecutive zeroes into groups
        groups += (zero // X)
 
    # Left variable will count
    # the consecutive zeroes
    #  on the left side of '1'
    left = 0
 
    # Right variable will count
    # the consecutive zeroes
    # on the right size of '1'
    right = 0
 
    # Iterating str from 0 index
    j = 0
    while (j < n):
 
        ch = str[j]
 
        # If it is '0' keep
        # incrementing left zeroes
        if (ch == '0'):
            left += 1
            j += 1
 
        # Else increment
        # right zeroes while
        # character is '0'
        else:
 
            k = j
            j += 1
            while (j < n and str[j] != '1'):
                j += 1
                right += 1
 
            contribute = (left + right + 1) // X
            without = ((left // X) + (right // X))
 
            # Checking after flipping
            # current '1' will
            # it affect the groups or not
            if (without != contribute):
                return 1 + groups
 
            #  If it doesn't affect
            #  then right zeroes
            # will become left zeroes
            # and for right
            # zeroes we will have
            # to count it again
            left = right
            right = 0
 
    # Return number of groups
    return groups
 
# Driver Code
str = "0010001"
X = 2
max_groups = maxGroupOfZeroes(str, X)
print(max_groups)
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# program of finding
// the maximum group of zeroes
// in a binary string after
// flipping at most one '1'
using System;
class GFG {
 
  // Function to find the maximum
  // number of groups of X
  // consecutive Zeroes
  public static int maxGroupOfZeroes(
    String str, int X)
  {
    int n = str.Length;
 
    // Number of groups before flipping '1'
    int groups = 0;
 
    // Iterating over the string
    int i = 0;
    while (i < n) {
 
      // It will keep the track
      // of consecutive zeroes
      int zero = 0;
      while (i < n
             && str[i] == '0') {
        zero++;
        i++;
      }
      i++;
 
      // It will break those
      // consecutive zeroes into groups
      groups += (zero / X);
    }
 
    // Left variable will count
    // the consecutive zeroes
    // on the left side of '1'
    int left = 0;
 
    // Right variable will count
    // the consecutive zeroes
    // on the right size of '1'
    int right = 0;
 
    // Iterating str from 0 index
    i = 0;
    while (i < n) {
 
      char ch = str[i];
 
      // If it is '0' keep
      // incrementing left zeroes
      if (ch == '0') {
        left++;
        i++;
      }
      // Else increment
      // right zeroes while
      // character is '0'
      else {
 
        int j = i;
        i++;
        while (i < n
               && str[i] != '1') {
          i++;
          right++;
        }
 
        int contribute
          = (left + right + 1) / X;
        int without
          = ((left / X) + (right / X));
 
        // Checking after flipping
        // current '1' will
        // it affect the groups or not
        if (without != contribute) {
          return ++groups;
        }
 
        // If it doesn't affect
        // then right zeroes
        // will become left zeroes
        // and for right
        // zeroes we will have
        // to count it again
        left = right;
        right = 0;
      }
    }
 
    // Return number of groups
    return groups;
  }
 
  // Driver Code
  public static void Main()
  {
    String str = "0010001";
    int X = 2;
    int max_groups
      = maxGroupOfZeroes(str, X);
    Console.Write(max_groups);
  }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

<script>
        // JavaScript code for the above approach
 
 
        // Function to find the maximum
        // number of groups of X
        // consecutive Zeroes
        function maxGroupOfZeroes(
            str, X) {
            let n = str.length;
 
            // Number of groups before flipping '1'
            let groups = 0;
 
            // Iterating over the string
            let i = 0;
            while (i < n) {
 
                // It will keep the track
                // of consecutive zeroes
                let zero = 0;
                while (i < n
                    && str[i] == '0') {
                    zero++;
                    i++;
                }
                i++;
 
                // It will break those
                // consecutive zeroes into groups
                groups += Math.floor((zero / X));
            }
 
            // Left variable will count
            // the consecutive zeroes
            // on the left side of '1'
            let left = 0;
 
            // Right variable will count
            // the consecutive zeroes
            // on the right size of '1'
            let right = 0;
 
            // Iterating str from 0 index
            i = 0;
            while (i < n) {
 
                let ch = str[i];
 
                // If it is '0' keep
                // incrementing left zeroes
                if (ch == '0') {
                    left++;
                    i++;
                }
                // Else increment
                // right zeroes while
                // character is '0'
                else {
 
                    let j = i;
                    i++;
                    while (i < n
                        && str[i] != '1') {
                        i++;
                        right++;
                    }
 
                    let contribute
                        = Math.floor((left + right + 1) / X);
                    let without
                        = (Math.floor((left / X) + (right / X)));
 
                    // Checking after flipping
                    // current '1' will
                    // it affect the groups or not
                    if (without != contribute) {
                        return ++groups;
                    }
 
                    // If it doesn't affect
                    // then right zeroes
                    // will become left zeroes
                    // and for right
                    // zeroes we will have
                    // to count it again
                    left = right;
                    right = 0;
                }
            }
 
            // Return number of groups
            return groups;
        }
 
        // Driver Code
 
        let str = "0010001";
        let X = 2;
        let max_groups
            = maxGroupOfZeroes(str, X);
        document.write(max_groups);
 
 
       // This code is contributed by Potta Lokesh
    </script>
Producción

3

Complejidad Temporal: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.

Publicación traducida automáticamente

Artículo escrito por Kdheeraj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *