Dada una string binaria S , la tarea es encontrar la string más pequeña posible eliminando todas las apariciones de las substrings “01” y “11” . Después de eliminar cualquier substring, concatene las partes restantes de la string.
Ejemplos:
Entrada: S = “0010110”
Salida:
Longitud = 1 String = 0
Explicación: La string se puede transformar mediante los siguientes pasos:
0 01 0110 → 0 01 10 → 01 0 → 0.
Dado que no quedan ocurrencias de las substrings 01 y 11, la string «0» tiene la longitud mínima posible 1.Entrada: S = “0011101111”
Salida: Longitud = 0
Explicación:
La string se puede transformar mediante los siguientes pasos:
0 01 1101111 → 0110 11 11 → 01 1011 → 1 01 1 → 11 → “”.
Planteamiento: Para resolver el problema, la idea es observar los siguientes casos:
- 01 y 11 significan que ?1 puede eliminarse donde ‘?’ puede ser 1 o 0 .
- La string final siempre tendrá la forma 1000… o 000…
Este problema se puede resolver manteniendo una pila mientras se procesa la string S dada de izquierda a derecha. Si el dígito binario actual es 0 , agréguelo a la pila, si el dígito binario actual es 1 , elimine el bit superior de la pila. Si la pila está vacía, empuje el bit actual a la pila. Siga los pasos a continuación para resolver el problema:
- Inicialice una pila para almacenar la string mínima posible.
- Recorre la string dada sobre el rango [0, N – 1] .
- Si la pila está vacía, inserte el dígito binario actual S[i] en la pila.
- Si la pila no está vacía y el bit actual S[i] es 1 , elimine el bit superior de la pila.
- Si el elemento actual S[i] es 0 entonces, empújelo a la pila.
- Finalmente, agrega todos los elementos presentes en la pila de arriba a abajo e imprímelo como resultado.
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
// length of the given string
void findMinLength(string s, int n)
{
// Initialize a stack
stack<int> st;
// Traverse the string
for (int i = 0; i < n; i++) {
// If the stack is empty
if (st.empty())
// Push the character
st.push(s[i]);
// If the character is 1
else if (s[i] == '1')
// Pop the top element
st.pop();
// Otherwise
else
// Push the character
// to the stack
st.push(s[i]);
}
// Initialize length
int ans = 0;
// Append the characters
// from top to bottom
vector<char> finalStr;
// Until Stack is empty
while (!st.empty()) {
ans++;
finalStr.push_back(st.top());
st.pop();
}
// Print the final string size
cout << "Length = " << ans;
// If length of the string is not 0
if (ans != 0) {
// Print the string
cout << "\nString = ";
for (int i = 0; i < ans; i++)
cout << finalStr[i];
}
}
// Driver Code
int main()
{
// Given string
string S = "101010";
// String length
int N = S.size();
// Function call
findMinLength(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find minimum
// length of the given string
static void findMinLength(String s, int n)
{
// Initialize a stack
Stack<Character> st = new Stack<>();
// Traverse the string
for(int i = 0; i < n; i++)
{
// If the stack is empty
if (st.empty())
// Push the character
st.push(s.charAt(i));
// If the character is 1
else if (s.charAt(i) == '1')
// Pop the top element
st.pop();
// Otherwise
else
// Push the character
// to the stack
st.push(s.charAt(i));
}
// Initialize length
int ans = 0;
// Append the characters
// from top to bottom
Vector<Character> finalStr = new Vector<Character>();
// Until Stack is empty
while (st.size() > 0)
{
ans++;
finalStr.add(st.peek());
st.pop();
}
// Print the final string size
System.out.println("Length = " + ans);
// If length of the string is not 0
if (ans != 0)
{
// Print the string
System.out.print("String = ");
for(int i = 0; i < ans; i++)
System.out.print(finalStr.get(i));
}
}
// Driver Code
public static void main(String args[])
{
// Given string
String S = "101010";
// String length
int N = S.length();
// Function call
findMinLength(S, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program for the above approach
from collections import deque
# Function to find minimum length
# of the given string
def findMinLength(s, n):
# Initialize a stack
st = deque()
# Traverse the string from
# left to right
for i in range(n):
# If the stack is empty,
# push the character
if (len(st) == 0):
st.append(s[i])
# If the character
# is B, pop from stack
elif (s[i] == '1'):
st.pop()
# Otherwise, push the
# character to the stack
else:
st.append(s[i])
# Stores resultant string
ans = 0
finalStr = []
while (len(st) > 0):
ans += 1
finalStr.append(st[-1]);
st.pop()
# Print the final string size
print("The final string size is: ", ans)
# If length is not 0
if (ans == 0):
print("The final string is: EMPTY")
# Print the string
else:
print("The final string is: ", *finalStr)
# Driver Code
if __name__ == '__main__':
# Given string
s = "0010110"
# String length
n = 7
# Function Call
findMinLength(s, n)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum
// length of the given string
static void findMinLength(String s, int n)
{
// Initialize a stack
Stack<char> st = new Stack<char>();
// Traverse the string
for(int i = 0; i < n; i++)
{
// If the stack is empty
if (st.Count == 0)
// Push the character
st.Push(s[i]);
// If the character is 1
else if (s[i] == '1')
// Pop the top element
st.Pop();
// Otherwise
else
// Push the character
// to the stack
st.Push(s[i]);
}
// Initialize length
int ans = 0;
// Append the characters
// from top to bottom
List<char> finalStr = new List<char>();
// Until Stack is empty
while (st.Count > 0)
{
ans++;
finalStr.Add(st.Peek());
st.Pop();
}
// Print the readonly string size
Console.WriteLine("Length = " + ans);
// If length of the string is not 0
if (ans != 0)
{
// Print the string
Console.Write("String = ");
for(int i = 0; i < ans; i++)
Console.Write(finalStr[i]);
}
}
// Driver Code
public static void Main(String []args)
{
// Given string
String S = "101010";
// String length
int N = S.Length;
// Function call
findMinLength(S, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to find minimum
// length of the given string
function findMinLength(s, n)
{
// Initialize a stack
var st = [];
// Traverse the string
for (var i = 0; i < n; i++) {
// If the stack is empty
if (st.length==0)
// Push the character
st.push(s[i]);
// If the character is 1
else if (s[i] == '1')
// Pop the top element
st.pop();
// Otherwise
else
// Push the character
// to the stack
st.push(s[i]);
}
// Initialize length
var ans = 0;
// Append the characters
// from top to bottom
var finalStr = [];
// Until Stack is empty
while (st.length!=0) {
ans++;
finalStr.push(st[st.length-1]);
st.pop();
}
// Print the final string size
document.write( "Length = " + ans);
// If length of the string is not 0
if (ans != 0) {
// Print the string
document.write( "<br>String = ");
for(var i = 0; i < ans; i++)
document.write( finalStr[i]);
}
}
// Driver Code
// Given string
var S = "101010";
// String length
var N = S.length;
// Function call
findMinLength(S, N);
</script>
Producción:
Length = 2 String = 01
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shailjapriya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA