Una secuencia equilibrada se define como una string en la que por cada paréntesis de apertura hay 2 paréntesis de cierre continuos. Por lo tanto, {}}, {{}}}}, {{}}{}}}} están balanceados, mientras que }}{, {} no lo están.
Ahora, dada una secuencia de corchetes (‘{‘ y ‘}’), puede realizar solo una operación en esa secuencia, es decir, insertar un corchete de apertura o de cierre en cualquier posición. Tienes que decir el número mínimo de operaciones necesarias para equilibrar la secuencia dada.
Entrada: str = “{}}”
Salida: 0
La secuencia ya está balanceada.
Entrada: str = “{}{}}}”
Salida: 3
La secuencia actualizada será “{} } {}} {} }”.
Enfoque: Para hacer una secuencia equilibrada, se requieren dos paréntesis de cierre continuos para cada paréntesis de apertura. Puede haber 3 casos:
- Cuando el carácter actual es un corchete de apertura: si el carácter anterior no es un corchete de cierre, simplemente inserte el corchete de apertura para apilar, de lo contrario, se necesita un corchete de cierre que costará una operación.
- Si la pila está vacía y el carácter actual es un corchete de cierre: En este caso, se requiere un corchete de apertura que costará una operación e insertará ese corchete de apertura en la pila.
- Si la pila no está vacía pero el carácter actual es un corchete de cierre: aquí, solo se requiere el recuento de corchetes de cierre. Si es 2, elimine un paréntesis de apertura de la pila; de lo contrario, incremente la cuenta del paréntesis de cierre.
Al final de la string, si la pila no está vacía, entonces el conteo requerido de paréntesis de cierre será ((2 * tamaño de la pila) – conteo actual de corchetes de cierre).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum operations required
int minOperations(string s, int len)
{
int operationCnt = 0;
stack<char> st;
int cntClosing = 0;
for (int i = 0; i < len; i++) {
// Condition where we got only one closing
// bracket instead of 2, here we have to
// add one more closing bracket to
// make the sequence balanced
if (s[i] == '{') {
if (cntClosing > 0) {
// Add closing bracket that
// costs us one operation
operationCnt++;
// Remove the top opening bracket because
// we got the 1 opening and 2
// continuous closing brackets
st.pop();
}
// Inserting the opening bracket to stack
st.push(s[i]);
// After making the sequence balanced
// closing is now set to 0
cntClosing = 0;
}
else if (st.empty()) {
// Case when there is no opening bracket
// the sequence starts with a closing bracket
// and one opening bracket is required
// Now we have one opening and one closing bracket
st.push('{');
// Add opening bracket that
// costs us one operation
operationCnt++;
// Assigning 1 to cntClosing because
// we have one closing bracket
cntClosing = 1;
}
else {
cntClosing = (cntClosing + 1) % 2;
// Case where we got two continuous closing brackets
// Need to pop one opening bracket from stack top
if (cntClosing == 0) {
st.pop();
}
}
}
// Condition where stack is not empty
// This is the case where we have
// only opening brackets
// (st.size() * 2) will give us the total
// closing bracket needed
// cntClosing is the count of closing
// bracket that we already have
operationCnt += st.size() * 2 - cntClosing;
return operationCnt;
}
// Driver code
int main()
{
string str = "}}{";
int len = str.length();
cout << minOperations(str, len);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG{
// Function to return the
// minimum operations required
static int minOperations(String s, int len)
{
int operationCnt = 0;
Stack<Character> st = new Stack<Character>();
int cntClosing = 0;
for(int i = 0; i < len; i++)
{
// Condition where we got only one
// closing bracket instead of 2,
// here we have to add one more
// closing bracket to make the
// sequence balanced
if (s.charAt(i) == '{')
{
if (cntClosing > 0)
{
// Add closing bracket that
// costs us one operation
operationCnt++;
// Remove the top opening bracket
// because we got the 1 opening
// and 2 continuous closing brackets
st.pop();
}
// Inserting the opening bracket to stack
st.add(s.charAt(i));
// After making the sequence balanced
// closing is now set to 0
cntClosing = 0;
}
else if (st.isEmpty())
{
// Case when there is no opening
// bracket the sequence starts
// with a closing bracket and
// one opening bracket is required
// Now we have one opening and one
// closing bracket
st.add('{');
// Add opening bracket that
// costs us one operation
operationCnt++;
// Assigning 1 to cntClosing because
// we have one closing bracket
cntClosing = 1;
}
else
{
cntClosing = (cntClosing + 1) % 2;
// Case where we got two continuous
// closing brackets need to pop one
// opening bracket from stack top
if (cntClosing == 0)
{
st.pop();
}
}
}
// Condition where stack is not empty
// This is the case where we have only
// opening brackets (st.size() * 2)
// will give us the total closing
// bracket needed cntClosing is the
// count of closing bracket that
// we already have
operationCnt += st.size() * 2 - cntClosing;
return operationCnt;
}
// Driver code
public static void main(String[] args)
{
String str = "}}{";
int len = str.length();
System.out.print(minOperations(str, len));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation
# of the approach
# Function to return the
# minimum operations required
def minOperations(s, length):
operationCnt = 0
stack = [] # Built-in Python3 list to implement stack
cntClosing = 0
for i in range(0, length):
# Condition where we got only one
# closing bracket instead of 2,
# here we have to add one more
# closing bracket to make the
# sequence balanced
if (s[i] == '{'):
if (cntClosing > 0):
# Add closing bracket that
# costs us one operation
operationCnt += 1
# Remove the top opening bracket
# because we got the 1 opening
# and 2 continuous closing brackets
stack.pop()
# Inserting the opening bracket to stack
stack.append(s[i])
# After making the sequence balanced
# closing is now set to 0
cntClosing = 0
elif not stack:
# Case when there is no opening
# bracket the sequence starts
# with a closing bracket and
# one opening bracket is required
# Now we have one opening and one
# closing bracket
stack.append('{')
# Add opening bracket that
# costs us one operation
operationCnt += 1
# Assigning 1 to cntClosing because
# we have one closing bracket
cntClosing = 1
else:
cntClosing = (cntClosing + 1) % 2
# Case where we got two continuous
# closing brackets need to pop one
# opening bracket from stack top
if (cntClosing == 0):
stack.pop()
# Condition where stack is not empty
# This is the case where we have only
# opening brackets (st.size() * 2)
# will give us the total closing
# bracket needed cntClosing is the
# count of closing bracket that
# we already have
operationCnt += len(stack) * 2 - cntClosing
return operationCnt
# Driver code
if __name__ == '__main__':
string = "}}{"
print(minOperations(string, len(string)))
# This code is contributed by gauravrajput1
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the
// minimum operations required
static int minOperations(String s,
int len)
{
int operationCnt = 0;
Stack<char> st = new Stack<char>();
int cntClosing = 0;
for(int i = 0; i < len; i++)
{
// Condition where we got only one
// closing bracket instead of 2,
// here we have to add one more
// closing bracket to make the
// sequence balanced
if (s[i] == '{')
{
if (cntClosing > 0)
{
// Add closing bracket that
// costs us one operation
operationCnt++;
// Remove the top opening bracket
// because we got the 1 opening
// and 2 continuous closing brackets
st.Pop();
}
// Inserting the opening bracket to stack
st.Push(s[i]);
// After making the sequence balanced
// closing is now set to 0
cntClosing = 0;
}
else if (st.Count != 0)
{
// Case when there is no opening
// bracket the sequence starts
// with a closing bracket and
// one opening bracket is required
// Now we have one opening and one
// closing bracket
st.Push('{');
// Add opening bracket that
// costs us one operation
operationCnt++;
// Assigning 1 to cntClosing because
// we have one closing bracket
cntClosing = 1;
}
else
{
cntClosing = (cntClosing + 1) % 2;
// Case where we got two continuous
// closing brackets need to pop one
// opening bracket from stack top
if (cntClosing == 0 &&
st.Count != 0)
{
st.Pop();
}
}
}
// Condition where stack is not empty
// This is the case where we have only
// opening brackets (st.Count * 2)
// will give us the total closing
// bracket needed cntClosing is the
// count of closing bracket that
// we already have
operationCnt += st.Count * 2 -
cntClosing + 1;
return operationCnt;
}
// Driver code
public static void Main(String[] args)
{
String str = "}}{";
int len = str.Length;
Console.Write(minOperations(str,
len));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum operations required
function minOperations(s, len)
{
var operationCnt = 0;
var st = [];
var cntClosing = 0;
for (var i = 0; i < len; i++) {
// Condition where we got only one closing
// bracket instead of 2, here we have to
// add one more closing bracket to
// make the sequence balanced
if (s[i] == '{') {
if (cntClosing > 0) {
// Add closing bracket that
// costs us one operation
operationCnt++;
// Remove the top opening bracket because
// we got the 1 opening and 2
// continuous closing brackets
st.pop();
}
// Inserting the opening bracket to stack
st.push(s[i]);
// After making the sequence balanced
// closing is now set to 0
cntClosing = 0;
}
else if (st.length==0) {
// Case when there is no opening bracket
// the sequence starts with a closing bracket
// and one opening bracket is required
// Now we have one opening and one closing bracket
st.push('{');
// Add opening bracket that
// costs us one operation
operationCnt++;
// Assigning 1 to cntClosing because
// we have one closing bracket
cntClosing = 1;
}
else {
cntClosing = (cntClosing + 1) % 2;
// Case where we got two continuous closing brackets
// Need to pop one opening bracket from stack top
if (cntClosing == 0) {
st.pop();
}
}
}
// Condition where stack is not empty
// This is the case where we have
// only opening brackets
// (st.size() * 2) will give us the total
// closing bracket needed
// cntClosing is the count of closing
// bracket that we already have
operationCnt += st.length * 2 - cntClosing;
return operationCnt;
}
// Driver code
var str = "}}{";
var len = str.length;
document.write( minOperations(str, len));
</script>
Producción:
3