Dada la string binaria str de longitud N , la tarea es encontrar el número mínimo de caracteres necesarios para eliminar de la string binaria dada para hacer una substring de 0 s seguida de una substring de 1 s.
Ejemplos:
Entrada: str = “00101101”
Salida: 2
Explicación: Eliminar str[2] y str[6] o eliminar str[3] y str[6] modifica la string binaria dada a “000111” o “001111” respectivamente. El número de eliminaciones necesarias en ambos casos es de 2, que es el mínimo posible.Entrada: str = “111000001111”
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la string y, por cada ‘1’ encontrado, calcular el número mínimo de eliminaciones requeridas eliminando 0 s o eliminando 1 s. Finalmente, imprima las eliminaciones mínimas requeridas.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar al tener un espacio auxiliar que lleva la cuenta del número de 0 después de 1 . Usando este cálculo previo, la complejidad del tiempo se puede mejorar por un factor de N. A continuación se muestran los pasos:
- Inicialice una variable, digamos ans , para almacenar la cantidad mínima de caracteres necesarios para eliminar.
- Inicialice una array , digamos zeroCount[] , para contar el número de 0 presentes después de un índice dado.
- Recorra la string str desde el final sobre el rango [N – 2, 0] y si el carácter actual es 0 , actualice zeroCount[i] como (zeroCount[i + 1] + 1) . De lo contrario, actualice zeroCount[i] como zeroCount[i + 1] .
- Inicialice una variable, digamos oneCount , para contar el número de 1s .
- Atraviesa la string dada de nuevo. Por cada carácter que se encuentre como ‘1’ , actualice ans como el mínimo de ans y (oneCount + zeroCount[i]) .
- Después de los pasos anteriores, si el valor de ans sigue siendo el mismo que su valor inicializado, se requieren 0 caracteres para eliminar. De lo contrario, ans es el número requerido de caracteres que se eliminarán.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to count minimum removals
// required to make a given string
// concatenation of substring of 0s
// followed by substring of 1s
int minimumDeletions(string s)
{
// Stores the length of the string
int n = s.size();
// Precompute the count of 0s
int zeroCount[n];
// Check for the last character
zeroCount[n - 1] = (s[n - 1] == '0') ? 1 : 0;
// Traverse and update zeroCount array
for(int i = n - 2; i >= 0; i--)
// If current character is 0,
zeroCount[i] = (s[i] == '0') ?
// Update aCount[i] as
// aCount[i + 1] + 1
zeroCount[i + 1] + 1 :
// Update as aCount[i + 1]
zeroCount[i + 1];
// Keeps track of deleted 1s
int oneCount = 0;
// Stores the count of removals
int ans = INT_MAX;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If current character is 1
if (s[i] == '1')
{
// Update ans
ans = min(ans,
oneCount +
zeroCount[i]);
oneCount++;
}
}
// If all 1s are deleted
ans = min(ans, oneCount);
// Return the minimum
// number of deletions
return (ans == INT_MAX) ? 0 : ans;
}
// Driver Code
int main()
{
string stri = "00101101";
cout << minimumDeletions(stri) << endl;
return 0;
}
// This code is contributed by AnkThon
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to count minimum removals
// required to make a given string
// concatenation of substring of 0s
// followed by substring of 1s
public static int minimumDeletions(String s)
{
// Stores the length of the string
int n = s.length();
// Precompute the count of 0s
int zeroCount[] = new int[n];
// Check for the last character
zeroCount[n - 1] = (s.charAt(n - 1)
== '0')
? 1
: 0;
// Traverse and update zeroCount array
for (int i = n - 2; i >= 0; i--)
// If current character is 0,
zeroCount[i] = (s.charAt(i) == '0')
// Update aCount[i] as
// aCount[i + 1] + 1
? zeroCount[i + 1] + 1
// Update as aCount[i + 1]
: zeroCount[i + 1];
// Keeps track of deleted 1s
int oneCount = 0;
// Stores the count of removals
int ans = Integer.MAX_VALUE;
// Traverse the array
for (int i = 0; i < n; i++) {
// If current character is 1
if (s.charAt(i) == '1') {
// Update ans
ans = Math.min(ans,
oneCount
+ zeroCount[i]);
oneCount++;
}
}
// If all 1s are deleted
ans = Math.min(ans, oneCount);
// Return the minimum
// number of deletions
return (ans == Integer.MAX_VALUE)
? 0
: ans;
}
// Driver Code
public static void main(String[] args)
{
String str = "00101101";
System.out.println(
minimumDeletions(str));
}
}
Python3
# Python3 program for the above approach # Function to count minimum removals # required to make a given string # concatenation of substring of 0s # followed by substring of 1s def minimumDeletions(s): # Stores the length of the string n = len(s) # Precompute the count of 0s zeroCount = [ 0 for i in range(n)] # Check for the last character zeroCount[n - 1] = 1 if s[n - 1] == '0' else 0 # Traverse and update zeroCount array for i in range(n - 2, -1, -1): # If current character is 0, zeroCount[i] = zeroCount[i + 1] + 1 if (s[i] == '0') else zeroCount[i + 1] # Keeps track of deleted 1s oneCount = 0 # Stores the count of removals ans = 10**9 # Traverse the array for i in range(n): # If current character is 1 if (s[i] == '1'): # Update ans ans = min(ans,oneCount + zeroCount[i]) oneCount += 1 # If all 1s are deleted ans = min(ans, oneCount) # Return the minimum # number of deletions return 0 if ans == 10**18 else ans # Driver Code if __name__ == '__main__': str = "00101101" print(minimumDeletions(str)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count minimum removals
// required to make a given string
// concatenation of substring of 0s
// followed by substring of 1s
public static int minimumDeletions(String s)
{
// Stores the length of the string
int n = s.Length;
// Precompute the count of 0s
int []zeroCount = new int[n];
// Check for the last character
zeroCount[n - 1] = (s[n - 1]
== '0')
? 1
: 0;
// Traverse and update zeroCount array
for (int i = n - 2; i >= 0; i--)
// If current character is 0,
zeroCount[i] = (s[i] == '0')
// Update aCount[i] as
// aCount[i + 1] + 1
? zeroCount[i + 1] + 1
// Update as aCount[i + 1]
: zeroCount[i + 1];
// Keeps track of deleted 1s
int oneCount = 0;
// Stores the count of removals
int ans = int.MaxValue;
// Traverse the array
for (int i = 0; i < n; i++) {
// If current character is 1
if (s[i] == '1') {
// Update ans
ans = Math.Min(ans,
oneCount
+ zeroCount[i]);
oneCount++;
}
}
// If all 1s are deleted
ans = Math.Min(ans, oneCount);
// Return the minimum
// number of deletions
return (ans == int.MaxValue)
? 0
: ans;
}
// Driver Code
public static void Main(String[] args)
{
String str = "00101101";
Console.WriteLine(
minimumDeletions(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for above approach
// Function to count minimum removals
// required to make a given string
// concatenation of substring of 0s
// followed by substring of 1s
function minimumDeletions(s)
{
// Stores the length of the string
let n = s.length;
// Precompute the count of 0s
let zeroCount = [];
// Check for the last character
zeroCount[n - 1] = (s[n - 1]
== '0')
? 1
: 0;
// Traverse and update zeroCount array
for (let i = n - 2; i >= 0; i--)
// If current character is 0,
zeroCount[i] = (s[i] == '0')
// Update aCount[i] as
// aCount[i + 1] + 1
? zeroCount[i + 1] + 1
// Update as aCount[i + 1]
: zeroCount[i + 1];
// Keeps track of deleted 1s
let oneCount = 0;
// Stores the count of removals
let ans = Number.MAX_VALUE;
// Traverse the array
for (let i = 0; i < n; i++) {
// If current character is 1
if (s[i] == '1') {
// Update ans
ans = Math.min(ans,
oneCount
+ zeroCount[i]);
oneCount++;
}
}
// If all 1s are deleted
ans = Math.min(ans, oneCount);
// Return the minimum
// number of deletions
return (ans == Number.MAX_VALUE)
? 0
: ans;
}
// Driver Code
let str = "00101101";
document.write(
minimumDeletions(str));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)