Dada una string binaria str de longitud N y un entero K donde K está en el rango (1 ≤ K ≤ N), la tarea es encontrar el número mínimo de vueltas (conversión de 0 s a 1 o viceversa) requeridas para ser realizado en la string dada de modo que la string resultante no contenga K o más ceros juntos.
Ejemplos:
Entrada: str = “11100000011”, K = 3
Salida: 2
Explicación:
Voltear los caracteres 6 y 7 modifica la string a “11100110011” . Por lo tanto, ninguna substring de 0 está presente en la string que tiene una longitud de 3 o más.Entrada: str = «110011», K = 1
Salida: 2
Invierta el tercer y cuarto carácter y luego str = «111111», que no contiene 1 o más ceros juntos.
Enfoque ingenuo: el enfoque más simple es generar todas las substrings posibles de la string dada y, para cada substring, verificar si consta solo de 0 o no. Si se encuentra que es cierto, verifique si su longitud excede K o no. Si se determina que es cierto, cuente el número de vueltas requeridas para esa substring. Finalmente, imprima el conteo de volteretas obtenidas.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: para hacer que el recuento de ceros contiguos en la string resultante sea menor que K , elija las substrings que constan solo de ceros de longitud ≥ K . Entonces, el problema se reduce a encontrar los cambios mínimos en cada substring. El resultado final será la suma de los giros mínimos de todos esos subsegmentos. A continuación se muestran los pasos:
- Inicialice el resultado a 0 y el recuento de ceros contiguos (por ejemplo, cnt_zeros ) a 0 .
- Atraviese la string y, al encontrar un ‘0’, incremente cnt_zeros en 1 .
- Si cnt_zeros se vuelve igual a K , incremente el resultado y establezca cnt_zeros en 0 .
- Y cuando aparece un ‘1’ , establezca cnt_zeros en 0 , ya que el recuento de ceros contiguos debería convertirse en 0 .
Debajo de la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return minimum
// number of flips required
int min_flips(string& str, int k)
{
// Base Case
if (str.size() == 0)
return 0;
// Stores the count of
// minimum number of flips
int ans = 0;
// Stores the count of zeros
// in current substring
int cnt_zeros = 0;
for (char ch : str) {
// If current character is 0
if (ch == '0') {
// Continue ongoing
// substring
++cnt_zeros;
}
else {
// Start a new substring
cnt_zeros = 0;
}
// If k consecutive
// zeroes are obtained
if (cnt_zeros == k) {
++ans;
// End segment
cnt_zeros = 0;
}
}
// Return the result
return ans;
}
// Driver Code
int main()
{
string str = "11100000011";
int k = 3;
// Function call
cout << min_flips(str, k);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to return minimum
// number of flips required
static int min_flips(String str, int k)
{
// Base Case
if (str.length() == 0)
return 0;
// Stores the count of
// minimum number of flips
int ans = 0;
// Stores the count of zeros
// in current subString
int cnt_zeros = 0;
for(char ch : str.toCharArray())
{
// If current character is 0
if (ch == '0')
{
// Continue ongoing
// subString
++cnt_zeros;
}
else
{
// Start a new subString
cnt_zeros = 0;
}
// If k consecutive
// zeroes are obtained
if (cnt_zeros == k)
{
++ans;
// End segment
cnt_zeros = 0;
}
}
// Return the result
return ans;
}
// Driver Code
public static void main(String[] args)
{
String str = "11100000011";
int k = 3;
// Function call
System.out.print(min_flips(str, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to return minimum # number of flips required def min_flips(strr, k): # Base Case if (len(strr) == 0): return 0 # Stores the count of # minimum number of flips ans = 0 # Stores the count of zeros # in current sub cnt_zeros = 0 for ch in strr: # If current character is 0 if (ch == '0'): # Continue ongoing # sub cnt_zeros += 1 else: # Start a new sub cnt_zeros = 0 # If k consecutive # zeroes are obtained if (cnt_zeros == k): ans += 1 # End segment cnt_zeros = 0 # Return the result return ans # Driver Code if __name__ == '__main__': strr = "11100000011" k = 3 # Function call print(min_flips(strr, k)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return minimum
// number of flips required
static int min_flips(String str, int k)
{
// Base Case
if (str.Length == 0)
return 0;
// Stores the count of
// minimum number of flips
int ans = 0;
// Stores the count of zeros
// in current subString
int cnt_zeros = 0;
foreach(char ch in str.ToCharArray())
{
// If current character is 0
if (ch == '0')
{
// Continue ongoing
// subString
++cnt_zeros;
}
else
{
// Start a new subString
cnt_zeros = 0;
}
// If k consecutive
// zeroes are obtained
if (cnt_zeros == k)
{
++ans;
// End segment
cnt_zeros = 0;
}
}
// Return the result
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String str = "11100000011";
int k = 3;
// Function call
Console.Write(min_flips(str, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the
// above approach
// Function to return minimum
// number of flips required
function min_flips(str, k)
{
// Base Case
if (str.length == 0)
return 0;
// Stores the count of
// minimum number of flips
let ans = 0;
// Stores the count of zeros
// in current subString
let cnt_zeros = 0;
for(let ch in str.split(''))
{
// If current character is 0
if (str[ch] == '0')
{
// Continue ongoing
// subString
++cnt_zeros;
}
else
{
// Start a new subString
cnt_zeros = 0;
}
// If k consecutive
// zeroes are obtained
if (cnt_zeros == k)
{
++ans;
// End segment
cnt_zeros = 0;
}
}
// Return the result
return ans;
}
// Driver Code
let str = "11100000011";
let k = 3;
// Function call
document.write(min_flips(str, k));
// This code is contributed by decode2207.
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)