Dada una string binaria str de tamaño N , la tarea es minimizar la longitud de la string binaria dada eliminando substrings de longitud uniforme que consisten en caracteres sam, es decir, 0 s o 1 s solamente, de la string cualquier cantidad de veces. Finalmente, imprima la string modificada.
Ejemplos:
Entrada: str =”101001″
Salida: “10”
Explicación: La string se puede minimizar de la siguiente manera: “101 00 1″ -> “10 11 ” -> “10”.Entrada: str = “00110”
Salida: “0”
Explicación: La string se puede minimizar de la siguiente manera: “ 00 110″ -> “ 11 0″ -> “0”.
Enfoque: La idea es usar una pila para resolver el problema. Mientras recorre la string , si se encuentra que el carácter actual es el mismo que el elemento superior de la pila , extraiga el elemento de la pila . Después del recorrido, imprima la pila de abajo hacia arriba. Siga los pasos a continuación para resolver el problema:
- Declare una pila y coloque el primer carácter de la string str en la pila.
- Recorra la string str sobre el rango de índices [1, N – 1] usando la variable i.
- Si la pila está vacía , inserte el carácter str[i] en la pila .
- De lo contrario, compruebe si str[i] es igual a la parte superior de la pila. Si se encuentra que es cierto, sáquelo de la pila . De lo contrario, inserte el carácter str[i] en él.
- Después de completar los pasos anteriores, imprima la pila de abajo hacia arriba .
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;
// Recursive function to print stack
// elements from bottom to top without
// changing their order
void PrintStack(stack<char> s)
{
// If stack is empty
if (s.empty())
return;
char x = s.top();
// Pop top element of the stack
s.pop();
// Recursively call the
// function PrintStack
PrintStack(s);
// Print the stack element
// from the bottom
cout << x;
// Push the same element onto the
// stack to preserve the order
s.push(x);
}
// Function to minimize binary string
// by removing substrings consisting
// of same character
void minString(string s)
{
// Declare a stack of characters
stack<char> Stack;
// Push the first character of
// the string into the stack
Stack.push(s[0]);
// Traverse the string s
for (int i = 1; i < s.size(); i++) {
// If Stack is empty
if (Stack.empty()) {
// Push current character
// into the stack
Stack.push(s[i]);
}
else {
// Check if the current
// character is same as
// the top of the stack
if (Stack.top() == s[i]) {
// If true, pop the
// top of the stack
Stack.pop();
}
// Otherwise, push the
// current element
else {
Stack.push(s[i]);
}
}
}
// Print stack from bottom to top
PrintStack(Stack);
}
// Driver Code
int main()
{
string str = "101001";
minString(str);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Recursive function to print stack
// elements from bottom to top without
// changing their order
static void PrintStack(Stack<Character> s)
{
// If stack is empty
if (s.isEmpty())
return;
char x = s.peek();
// Pop top element of the stack
s.pop();
// Recursively call the
// function PrintStack
PrintStack(s);
// Print the stack element
// from the bottom
System.out.print(x);
// Push the same element onto the
// stack to preserve the order
s.add(x);
}
// Function to minimize binary String
// by removing subStrings consisting
// of same character
static void minString(String s)
{
// Declare a stack of characters
Stack<Character> Stack = new Stack<Character>();
// Push the first character of
// the String into the stack
Stack.add(s.charAt(0));
// Traverse the String s
for (int i = 1; i < s.length(); i++) {
// If Stack is empty
if (Stack.isEmpty()) {
// Push current character
// into the stack
Stack.add(s.charAt(i));
}
else {
// Check if the current
// character is same as
// the top of the stack
if (Stack.peek() == s.charAt(i)) {
// If true, pop the
// top of the stack
Stack.pop();
}
// Otherwise, push the
// current element
else {
Stack.push(s.charAt(i));
}
}
}
// Print stack from bottom to top
PrintStack(Stack);
}
// Driver Code
public static void main(String[] args)
{
String str = "101001";
minString(str);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Recursive function to print stack # elements from bottom to top without # changing their order def PrintStack(s) : # If stack is empty if (len(s) == 0) : return; x = s[-1]; # Pop top element of the stack s.pop(); # Recursively call the # function PrintStack PrintStack(s); # Print the stack element # from the bottom print(x, end=""); # Push the same element onto the # stack to preserve the order s.append(x); # Function to minimize binary string # by removing substrings consisting # of same character def minString(s) : # Declare a stack of characters Stack = []; # Push the first character of # the string into the stack Stack.append(s[0]); # Traverse the string s for i in range(1, len(s)) : # If Stack is empty if (len(Stack) == 0) : # Push current character # into the stack Stack.append(s[i]); else: # Check if the current # character is same as # the top of the stack if (Stack[-1] == s[i]) : # If true, pop the # top of the stack Stack.pop(); # Otherwise, push the # current element else : Stack.append(s[i]); # Print stack from bottom to top PrintStack(Stack); # Driver Code if __name__ == "__main__" : string = "101001"; minString(string); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Recursive function to print stack
// elements from bottom to top without
// changing their order
static void PrintStack(Stack<char> s)
{
// If stack is empty
if (s.Count == 0)
return;
char x = s.Peek();
// Pop top element of the stack
s.Pop();
// Recursively call the
// function PrintStack
PrintStack(s);
// Print the stack element
// from the bottom
Console.Write((char)x);
// Push the same element onto the
// stack to preserve the order
s.Push(x);
}
// Function to minimize binary String
// by removing subStrings consisting
// of same character
static void minString(String s)
{
// Declare a stack of characters
Stack<char> Stack = new Stack<char>();
// Push the first character of
// the String into the stack
Stack.Push(s[0]);
// Traverse the String s
for (int i = 1; i < s.Length; i++)
{
// If Stack is empty
if (Stack.Count == 0)
{
// Push current character
// into the stack
Stack.Push(s[i]);
}
else
{
// Check if the current
// character is same as
// the top of the stack
if (Stack.Peek() == s[i])
{
// If true, pop the
// top of the stack
Stack.Pop();
}
// Otherwise, push the
// current element
else
{
Stack.Push(s[i]);
}
}
}
// Print stack from bottom to top
PrintStack(Stack);
}
// Driver Code
public static void Main(String[] args)
{
String str = "101001";
minString(str);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// js program for the above approach
// Recursive function to print stack
// elements from bottom to top without
// changing their order
function PrintStack( s)
{
// If stack is empty
if (s.length == 0)
return;
let x = s[s.length-1];
// Pop top element of the stack
s.pop();
// Recursively call the
// function PrintStack
PrintStack(s);
// Print the stack element
// from the bottom
document.write(x);
// Push the same element onto the
// stack to preserve the order
s.push(x);
}
// Function to minimize binary string
// by removing substrings consisting
// of same character
function minString( s)
{
// Declare a stack of characters
let Stack = [];
// Push the first character of
// the string into the stack
Stack.push(s[0]);
// Traverse the string s
for (let i = 1; i < s.length; i++) {
// If Stack is empty
if (Stack.length==0) {
// Push current character
// into the stack
Stack.push(s[i]);
}
else {
// Check if the current
// character is same as
// the top of the stack
if (Stack[Stack.length-1] == s[i]) {
// If true, pop the
// top of the stack
Stack.pop();
}
// Otherwise, push the
// current element
else {
Stack.push(s[i]);
}
}
}
// Print stack from bottom to top
PrintStack(Stack);
}
// Driver Code
let str = "101001";
minString(str);
</script>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shahbazalam75508 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA