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.