Dada una string binaria S , la tarea es encontrar el número mínimo de caracteres necesarios para eliminar de S , de modo que todos los 0 se coloquen antes de 1 s.
Ejemplos:
Entrada: S = “001101”
Salida: 1
Explicación:
Eliminar S[4] (= ‘0’) modifica la string S a “00111”.
Por lo tanto, el número mínimo de eliminaciones requeridas es 1.Entrada: S = 01001
Salida: 1
Explicación:
Eliminar S[1] (= ‘1’) modifica la string S a «0001».
Por lo tanto, el número mínimo de eliminaciones requeridas es 1.
Enfoque: el problema se puede resolver encontrando el número mínimo de caracteres ‘0’ que se requieren para eliminar desde la derecha, digamos right_0, y el número mínimo de ‘1’ que se requieren para eliminar desde la izquierda, digamos left_1 , para obtener la string requerida. La suma mínima de right_0 y left_0 obtenida para cualquier índice da el resultado final.
Siga los pasos a continuación para resolver el problema dado:
- Inicialice dos variables de contador, digamos right_0 y left_1 .
- Almacene el conteo de ‘0’ s en la string S en right_0 y establezca left_1 igual a 0 .
- Inicialice una variable, digamos res, para almacenar la respuesta requerida.
- Iterar sobre los caracteres de la string S y para cada carácter:
- Compruebe si s[i] es igual a ‘0’ o no.
- Si se determina que es cierto, disminuya right_0 en 1 .
- De lo contrario, aumente left_1 en 1 .
- Compruebe si la suma right_0, left_1 es menor que res o no. Si se determina que es cierto, actualice res igual al mínimo de res y right_0 + left_1.
- Compruebe si s[i] es igual a ‘0’ o no.
- Después de completar el recorrido de la array, imprima res como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum removals
// required to arrange all 0s before 1s
int minimumDeletions(string s)
{
// Count the occurrences of 0 in s
int right_0 = count(s.begin(), s.end(), '0');
int left_1 = 0;
// Size of the string
int n = s.size();
// Stores the minimum
// number of removals required
int res = INT_MAX;
// Iterate over each of the
// characters in the string s
for (int i = 0; i < n; i++)
{
// If the i-th character
// is found to be '0'
if (s[i] == '0')
{
right_0 -= 1;
}
else
{
left_1 += 1;
}
// Store the minimum of res
// and right_0 + left_1 in res
res = min(res, right_0 + left_1);
}
// Return the final result
return res;
}
// Driver Code
int main()
{
string s = "001101";
int count = minimumDeletions(s);
cout << count;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count minimum removals
// required to arrange all 0s before 1s
static int minimumDeletions(String s)
{
// Count the occurrences of 0 in s
int right_0 = (int)(s.chars().filter(ch -> ch == '0').count());
int left_1 = 0;
// Size of the string
int n = s.length();
// Stores the minimum
// number of removals required
int res = Integer.MAX_VALUE;
// Iterate over each of the
// characters in the string s
for (int i = 0; i < n; i++)
{
// If the i-th character
// is found to be '0'
if (s.charAt(i) == '0')
{
right_0 -= 1;
}
else
{
left_1 += 1;
}
// Store the minimum of res
// and right_0 + left_1 in res
res = Math.min(res, right_0 + left_1);
}
// Return the final result
return res;
}
// Driver Code
public static void main(String[] args)
{
String s = "001101";
int count = minimumDeletions(s);
System.out.print(count);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach
import sys
# Function to count minimum removals
# required to arrange all 0s before 1s
def minimumDeletions(s) :
# Count the occurrences of 0 in s
right_0 = s.count('0')
left_1 = 0
# Size of the string
n = len(s)
# Stores the minimum
# number of removals required
res = sys.maxsize
# Iterate over each of the
# characters in the string s
for i in range(n):
# If the i-th character
# is found to be '0'
if (s[i] == '0') :
right_0 -= 1
else :
left_1 += 1
# Store the minimum of res
# and right_0 + left_1 in res
res = min(res, right_0 + left_1)
# Return the final result
return res
# Driver Code
s = "001101"
count = minimumDeletions(s)
print( count)
# This code is contributed by splevel62.
C#
// C# program for above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to count minimum removals
// required to arrange all 0s before 1s
static int minimumDeletions(string s)
{
// Count the occurrences of 0 in s
int right_0 = (int)s.Split('0').Length - 1;
int left_1 = 0;
// Size of the string
int n = s.Length;
// Stores the minimum
// number of removals required
int res = Int32.MaxValue;
// Iterate over each of the
// characters in the string s
for (int i = 0; i < n; i++)
{
// If the i-th character
// is found to be '0'
if (s[i] == '0')
{
right_0 -= 1;
}
else
{
left_1 += 1;
}
// Store the minimum of res
// and right_0 + left_1 in res
res = Math.Min(res, right_0 + left_1);
}
// Return the final result
return res;
}
// Driver code
public static void Main(String[] args)
{
string s = "001101";
int count = minimumDeletions(s);
Console.WriteLine(count);
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
// JavaScript program for the above approach
// Function to count minimum removals
// required to arrange all 0s before 1s
function minimumDeletions(s)
{
// Count the occurrences of 0 in s
var right_0 = 0;
var i;
for (i=0;i<s.length;i++){
if(s[i]=='0')
right_0++;
}
var left_1 = 0;
// Size of the string
var n = s.length;
// Stores the minimum
// number of removals required
var res = 2147483647;
// Iterate over each of the
// characters in the string s
for (i = 0; i < n; i++)
{
// If the i-th character
// is found to be '0'
if (s[i] == '0')
{
right_0 -= 1;
}
else
{
left_1 += 1;
}
// Store the minimum of res
// and right_0 + left_1 in res
res = Math.min(res, right_0 + left_1);
}
// Return the final result
return res;
}
// Driver Code
var s = "001101";
var count = minimumDeletions(s);
document.write(count);
</script>
Producción:
1
Complejidad temporal: O(|S|)
Espacio auxiliar: O(1)