Dada una string binaria S que consta de N caracteres, la tarea es imprimir el número mínimo de operaciones requeridas para eliminar todos los caracteres de la string S dada eliminando un solo carácter o eliminando cualquier subsecuencia de caracteres alternativos en cada operación.
Ejemplos:
Entrada: S = “010101”
Salida: 1
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Considere la subsecuencia S[0, 5] es decir, “010101” ya que contiene caracteres alternos. Por lo tanto, eliminar esto modifica la string a «».
Por lo tanto, el número total de operaciones requeridas es 1.Entrada: S = “00011”
Salida: 3
Enfoque: el problema dado se puede resolver iterando sobre la string una vez y realizando un seguimiento del número máximo de 0 y 1 restantes . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans para almacenar el número máximo de 0 y 1 que aún quedan por eliminar, una variable cnt0 para contar el número de 0 y una variable cnt1 para contar el número de 1 .
- Recorra la string S dada desde el principio y realice los siguientes pasos:
- Si el carácter actual es 0 , aumente el valor de cnt0 en 1 y disminuya el valor de cnt1 en 1 si es mayor que 0 .
- Si el carácter actual es 1 , incremente el valor de cnt1 en 1 y disminuya el valor de cnt0 en 1 si es mayor que 0 .
- Actualice el valor de ans al máximo de ans , cnt1 y cnt0 .
- Después de completar los pasos anteriores, imprima el valor de ans como el número mínimo de operaciones requeridas para eliminar todos los caracteres.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of operations to empty a binary string
int minOpsToEmptyString(string s)
{
// Stores the resultant number of
// operations
int ans = INT_MIN;
// Stores the number of 0s
int cn0 = 0;
// Stores the number of 1s
int cn1 = 0;
// Traverse the given string
for (int i = 0;
i < s.length(); i++) {
if (s[i] == '0') {
// To balance 0 with 1
// if possible
if (cn1 > 0)
cn1--;
// Increment the value
// of cn0 by 1
cn0++;
}
else {
// To balance 1 with 0
// if possible
if (cn0 > 0)
cn0--;
// Increment the value
// of cn1
cn1++;
}
// Update the maximum number
// of unused 0s and 1s
ans = max({ ans, cn0, cn1 });
}
// Print the resultant count
cout << ans;
}
// Driver Code
int main()
{
string S = "010101";
minOpsToEmptyString(S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum number
// of operations to empty a binary string
static void minOpsToEmptyString(String s)
{
// Stores the resultant number of
// operations
int ans = Integer.MIN_VALUE;
// Stores the number of 0s
int cn0 = 0;
// Stores the number of 1s
int cn1 = 0;
// Traverse the given string
for(int i = 0; i < s.length(); i++)
{
if (s.charAt(i) == '0')
{
// To balance 0 with 1
// if possible
if (cn1 > 0)
cn1--;
// Increment the value
// of cn0 by 1
cn0++;
}
else
{
// To balance 1 with 0
// if possible
if (cn0 > 0)
cn0--;
// Increment the value
// of cn1
cn1++;
}
// Update the maximum number
// of unused 0s and 1s
ans = Math.max(ans, Math.max(cn0, cn1));
}
// Print the resultant count
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
String S = "010101";
minOpsToEmptyString(S);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find the minimum number # of operations to empty a binary string def minOpsToEmptyString(s): # Stores the resultant number of # operations ans = -10**9 # Stores the number of 0s cn0 = 0 # Stores the number of 1s cn1 = 0 # Traverse the given string for i in range(len(s)): if (s[i] == '0'): # To balance 0 with 1 # if possible if (cn1 > 0): cn1 -= 1 # Increment the value # of cn0 by 1 cn0 += 1 else: # To balance 1 with 0 # if possible if (cn0 > 0): cn0 -= 1 # Increment the value # of cn1 cn1 += 1 # Update the maximum number # of unused 0s and 1s ans = max([ans, cn0, cn1]) # Print resultant count print (ans) # Driver Code if __name__ == '__main__': S = "010101" minOpsToEmptyString(S) # 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 find the minimum number
// of operations to empty a binary string
static void minOpsToEmptyString(string s)
{
// Stores the resultant number of
// operations
int ans = 0;
// Stores the number of 0s
int cn0 = 0;
// Stores the number of 1s
int cn1 = 0;
// Traverse the given string
for(int i = 0; i < s.Length; i++)
{
if (s[i] == '0')
{
// To balance 0 with 1
// if possible
if (cn1 > 0)
cn1--;
// Increment the value
// of cn0 by 1
cn0++;
}
else
{
// To balance 1 with 0
// if possible
if (cn0 > 0)
cn0--;
// Increment the value
// of cn1
cn1++;
}
// Update the maximum number
// of unused 0s and 1s
ans = Math.Max(ans, Math.Max(cn0, cn1));
}
// Print the resultant count
Console.Write(ans);
}
// Driver Code
public static void Main()
{
string S = "010101";
minOpsToEmptyString(S);
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum number
// of operations to empty a binary string
function minOpsToEmptyString(s)
{
// Stores the resultant number of
// operations
var ans = Number.MIN_VALUE;
// Stores the number of 0s
var cn0 = 0;
// Stores the number of 1s
var cn1 = 0;
// Traverse the given string
for(var i = 0; i < s.length; i++)
{
if (s.charAt(i) == '0')
{
// To balance 0 with 1
// if possible
if (cn1 > 0)
cn1--;
// Increment the value
// of cn0 by 1
cn0++;
}
else
{
// To balance 1 with 0
// if possible
if (cn0 > 0)
cn0--;
// Increment the value
// of cn1
cn1++;
}
// Update the maximum number
// of unused 0s and 1s
ans = Math.max(ans, Math.max(cn0, cn1));
}
// Print the resultant count
document.write(ans);
}
// Driver Code
var S = "010101";
minOpsToEmptyString(S);
//This code is contributed by shivanisinghss2110
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shauryarehangfg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA