Dada una string binaria , str , la tarea es vaciar la string dada por el número mínimo de eliminaciones de un solo carácter o una subsecuencia que contenga distintos caracteres consecutivos de str .
Ejemplos:
Entrada: str = “0100100111”
Salida: 3
Explicación:
Eliminar la subsecuencia “010101” de la string modifica str a “0011”.
Eliminar la subsecuencia «01» de la string modifica str a «01».
Eliminar la subsecuencia «01» de la string modifica str a «», que es una string vacía.
Por lo tanto, la salida requerida es 3.Entrada: str = “010110”
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es recorrer la string de forma repetitiva y eliminar la subsecuencia más larga de caracteres consecutivos distintos de la string e incrementar el recuento después de cada eliminación. Finalmente, imprima el conteo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver utilizando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos cntOne y cntZero , para almacenar el conteo de 1 s y 0 s.
- Recorra la string usando la variable i y verifique las siguientes condiciones:
- Si str[i] == ‘0’ , incremente el valor de cntZero y verifique si el valor de cntOne es mayor que 0 o no. Si se determina que es cierto, disminuya el valor de cntOne .
- Si str[i] == ‘1’ , entonces incremente el valor de cntOne y verifique si el valor de cntZero es mayor que 0 o no. Si se determina que es cierto, disminuya el valor de cntZero .
- Finalmente, imprima el valor de (cntZero + cntOne) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
//Function to count minimum operations required
// to make the string an empty string
int findMinOperationsReqEmpStr(string str)
{
// Stores count of 1s by removing
// consecutive distinct subsequence
int cntOne = 0;
// Stores count of 0s by removing
// consecutive distinct subsequence
int cntZero = 0 ;
// Stores length of str
int N = str.length();
// Traverse the string
for (int i = 0; i < N; i++) {
// If current character
// is 0
if(str[i] == '0'){
if (cntOne) {
// Update cntOne
cntOne--;
}
// Update cntZero
cntZero++;
}
// If current character
// is 1
else{
//Update cntZero
if (cntZero) {
cntZero--;
}
// Update cntOne
cntOne++;
}
}
return (cntOne + cntZero);
}
// Driver Code
int main()
{
string str = "0100100111";
cout<< findMinOperationsReqEmpStr(str);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG{
//Function to count minimum operations required
// to make the string an empty string
static int findMinOperationsReqEmpStr(String str)
{
// Stores count of 1s by removing
// consecutive distinct subsequence
int cntOne = 0;
// Stores count of 0s by removing
// consecutive distinct subsequence
int cntZero = 0;
// Stores length of str
int N = str.length();
// Traverse the string
for(int i = 0; i < N; i++)
{
// If current character
// is 0
if(str.charAt(i) == '0')
{
if (cntOne != 0)
{
// Update cntOne
cntOne--;
}
// Update cntZero
cntZero++;
}
// If current character
// is 1
else
{
// Update cntZero
if (cntZero != 0)
{
cntZero--;
}
// Update cntOne
cntOne++;
}
}
return (cntOne + cntZero);
}
// Driver code
public static void main(String[] args)
{
String str = "0100100111";
System.out.print(findMinOperationsReqEmpStr(str));
}
}
// This code is contributed by ajaykr00kj
Python3
# Python3 program to implement # the above approach # Function to count minimum operations # required to make the string an empty # string def findMinOperationsReqEmpStr(str): # Stores count of 1s by removing # consecutive distinct subsequence cntOne = 0 # Stores count of 0s by removing # consecutive distinct subsequence cntZero = 0 # Traverse the string for element in str: # If current character # is 0 if element == '0': if cntOne > 0: # Update cntOne cntOne = cntOne - 1 # Update cntZero cntZero = cntZero + 1 # If current character # is 1 else: # Update cntZero if cntZero > 0: cntZero = cntZero - 1 # Update cntOne cntOne = cntOne + 1 return cntOne + cntZero # Driver code if __name__ == "__main__": str = "0100100111" print(findMinOperationsReqEmpStr(str)) # This code is contributed by ajaykr00kj
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to count minimum operations required
// to make the string an empty string
static int findMinOperationsReqEmpStr(String str)
{
// Stores count of 1s by removing
// consecutive distinct subsequence
int cntOne = 0;
// Stores count of 0s by removing
// consecutive distinct subsequence
int cntZero = 0;
// Stores length of str
int N = str.Length;
// Traverse the string
for(int i = 0; i < N; i++)
{
// If current character
// is 0
if(str[i] == '0')
{
if (cntOne != 0)
{
// Update cntOne
cntOne--;
}
// Update cntZero
cntZero++;
}
// If current character
// is 1
else
{
// Update cntZero
if (cntZero != 0)
{
cntZero--;
}
// Update cntOne
cntOne++;
}
}
return (cntOne + cntZero);
}
// Driver code
public static void Main(String[] args)
{
String str = "0100100111";
Console.Write(findMinOperationsReqEmpStr(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count minimum operations required
// to make the string an empty string
function findMinOperationsReqEmpStr(str)
{
// Stores count of 1s by removing
// consecutive distinct subsequence
let cntOne = 0;
// Stores count of 0s by removing
// consecutive distinct subsequence
let cntZero = 0;
// Stores length of str
let N = str.length;
// Traverse the string
for(let i = 0; i < N; i++)
{
// If current character
// is 0
if (str[i] == '0')
{
if (cntOne != 0)
{
// Update cntOne
cntOne--;
}
// Update cntZero
cntZero++;
}
// If current character
// is 1
else
{
// Update cntZero
if (cntZero != 0)
{
cntZero--;
}
// Update cntOne
cntOne++;
}
}
return (cntOne + cntZero);
}
// Driver code
let str = "0100100111";
document.write(findMinOperationsReqEmpStr(str));
// This code is contributed by code_hunt
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA