Dada una string binaria S de longitud N , la tarea es encontrar el número mínimo de eliminación de caracteres adyacentes similares necesarios para vaciar la string binaria dada .
Ejemplos:
Entrada: S = «1100011»
Salida: 2
Explicación:
Operación 1: La eliminación de todos los 0 modifica S a «1111».
Operación 2: La eliminación de todos los 1 restantes hace que S quede vacío.
Por lo tanto, el número mínimo de operaciones requeridas es 2.Entrada: S = “0010100“
Salida: 3
Explicación:
Operación 1: La eliminación de todos los 1 modifica S a “000100“.
Operación 2: La eliminación de todos los 1 modifica S = «00000».
Operación 3: La eliminación de todos los 0 restantes hace que S quede vacío.
Por lo tanto, el número mínimo de operaciones requeridas es de 3.
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La idea es eliminar las apariciones consecutivas del personaje con mayor frecuencia. Siga los pasos a continuación para resolver el problema:
- Atraviese la string S dada y genere una nueva string, digamos newString , eliminando las ocurrencias consecutivas del carácter con mayor frecuencia.
- Finalmente, imprime (sizeof(newString) + 1)/2 como la respuesta requerida
Explicación : la string dada, por ejemplo: «1100011» cambia 101 ya que estamos saltando la ocurrencia múltiple. Después de esto, devolvemos (sizeof(newString) + 1)/2 el tamaño de la nueva string es 3, 101 -> primero eliminamos el 0, lo que nos lleva 1 operación, luego la nueva string es 11 , luego hacemos solo 1 operación más para eliminar la string 11, tomando un total de 2 operaciones.
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 find minimum steps // to make the string empty int minSteps(string S) { // Stores the modified string string new_str; // Size of string int N = S.length(); int i = 0; while (i < N) { new_str += S[i]; // Removing substring of same // character from modified string int j = i; while (i < N && S[i] == S[j]) ++i; } // Print the minimum steps required cout << ceil((new_str.size() + 1) / 2.0); } // Driver Code int main() { // Given string S string S = "0010100"; // Function Call minSteps(S); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find minimum steps // to make the String empty static void minSteps(String S) { // Stores the modified String String new_str = ""; // Size of String int N = S.length(); int i = 0; while (i < N) { new_str += S.charAt(i); // Removing subString of same // character from modified String int j = i; while (i < N && S.charAt(i) == S.charAt(j)) ++i; } // Print the minimum steps required System.out.print((int)Math.ceil( (new_str.length() + 1) / 2.0)); } // Driver Code public static void main(String[] args) { // Given String S String S = "0010100"; // Function Call minSteps(S); } } // This code is contributed by Princi Singh
Python3
# Python3 program for the above approach from math import ceil # Function to find minimum steps # to make the empty def minSteps(S): # Stores the modified string new_str = "" # Size of string N = len(S) i = 0 while (i < N): new_str += S[i] # Removing substring of same character # from modified string j = i while (i < N and S[i] == S[j]): i += 1 # Print the minimum steps required print(ceil((len(new_str) + 1) / 2)) # Driver Code if __name__ == '__main__': # Given S S = "0010100" # Function Call minSteps(S) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG{ // Function to find minimum steps // to make the string empty static void minSteps(string S) { // Stores the modified string string new_str = ""; // Size of string int N = S.Length; int i = 0; while (i < N) { new_str += S[i]; // Removing substring of same // character from modified string int j = i; while (i < N && S[i] == S[j]) ++i; } // Print the minimum steps required Console.Write((int)Math.Ceiling( (new_str.Length + 1) / 2.0)); } // Driver Code public static void Main() { // Given string S string S = "0010100"; // Function Call minSteps(S); } } // This code is contributed by SURENDRA_GANGWAR
Javascript
<script> // Javascript program to implement // the above approach // Function to find minimum steps // to make the string empty function minSteps(S) { // Stores the modified string let new_str = ""; // Size of string let N = S.length; let i = 0; while (i < N) { new_str += S[i]; // Removing substring of same // character from modified string let j = i; while (i < N && S[i] == S[j]) ++i; } // Print the minimum steps required document.write(Math.ceil( (new_str.length + 1) / 2.0)); } // Driver Code // Given string S let S = "0010100"; // Function Call minSteps(S) </script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA