Dada una secuencia de paréntesis no balanceada de ‘(‘ y ‘)’ , conviértala en una secuencia balanceada agregando el número mínimo de ‘(‘ al comienzo de la string y ‘)’ al final de la string.
Ejemplos:
Entrada: str = “)))()”
Salida: “((()))()”Entrada: str = “())())(())())”
Salida: “(((())())(())())”
Acercarse:
- Supongamos que cada vez que nos encontramos con un paréntesis de apertura la profundidad aumenta en uno y con un paréntesis de cierre la profundidad disminuye en uno.
- Encuentre la profundidad negativa máxima en minDep y agregue ese número de ‘(‘ al principio.
- Luego haga un bucle en la nueva secuencia para encontrar el número de ‘) necesarios al final de la string y agréguelos.
- Finalmente, devuelva la string.
A continuación se muestra la implementación del enfoque:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return balancedBrackets string
string balancedBrackets(string str)
{
// Initializing dep to 0
int dep = 0;
// Stores maximum negative depth
int minDep = 0;
for (int i = 0; i < str.length(); i++)
{
if (str[i] == '(')
dep++;
else
dep--;
// if dep is less than minDep
if (minDep > dep)
minDep = dep;
}
// if minDep is less than 0 then there
// is need to add '(' at the front
if (minDep < 0)
{
for (int i = 0; i < abs(minDep); i++)
str = '(' + str;
}
// Reinitializing to check the updated string
dep = 0;
for (int i = 0; i < str.length(); i++)
{
if (str[i] == '(')
dep++;
else
dep--;
}
// if dep is not 0 then there
// is need to add ')' at the back
if (dep != 0)
{
for (int i = 0; i < dep; i++)
str = str + ')';
}
return str;
}
// Driver code
int main()
{
string str = ")))()";
cout << balancedBrackets(str);
}
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to return balancedBrackets string
static String balancedBrackets(String str)
{
// Initializing dep to 0
int dep = 0;
// Stores maximum negative depth
int minDep = 0;
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) == '(')
dep++;
else
dep--;
// if dep is less than minDep
if (minDep > dep)
minDep = dep;
}
// if minDep is less than 0 then there
// is need to add '(' at the front
if (minDep < 0)
{
for (int i = 0; i < Math.abs(minDep); i++)
str = '(' + str;
}
// Reinitializing to check the updated string
dep = 0;
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) == '(')
dep++;
else
dep--;
}
// if dep is not 0 then there
// is need to add ')' at the back
if (dep != 0)
{
for (int i = 0; i < dep; i++)
str = str + ')';
}
return str;
}
// Driver code
public static void main(String[] args)
{
String str = ")))()";
System.out.println(balancedBrackets(str));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach
# Function to return balancedBrackets String
def balancedBrackets(Str):
# Initializing dep to 0
dep = 0
# Stores maximum negative depth
minDep = 0
for i in Str:
if (i == '('):
dep += 1
else:
dep -= 1
# if dep is less than minDep
if (minDep > dep):
minDep = dep
# if minDep is less than 0 then there
# is need to add '(' at the front
if (minDep < 0):
for i in range(abs(minDep)):
Str = '(' + Str
# Reinitializing to check the updated String
dep = 0
for i in Str:
if (i == '('):
dep += 1
else:
dep -= 1
# if dep is not 0 then there
# is need to add ')' at the back
if (dep != 0):
for i in range(dep):
Str = Str + ')'
return Str
# Driver code
Str = ")))()"
print(balancedBrackets(Str))
# This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return balancedBrackets string
static string balancedBrackets(string str)
{
// Initializing dep to 0
int dep = 0;
// Stores maximum negative depth
int minDep = 0;
for (int i = 0; i < str.Length; i++)
{
if (str[i] == '(')
dep++;
else
dep--;
// if dep is less than minDep
if (minDep > dep)
minDep = dep;
}
// if minDep is less than 0 then there
// is need to add '(' at the front
if (minDep < 0)
{
for (int i = 0; i < Math.Abs(minDep); i++)
str = '(' + str;
}
// Reinitializing to check the updated string
dep = 0;
for (int i = 0; i < str.Length; i++)
{
if (str[i] == '(')
dep++;
else
dep--;
}
// if dep is not 0 then there
// is need to add ')' at the back
if (dep != 0)
{
for (int i = 0; i < dep; i++)
str = str + ')';
}
return str;
}
// Driver code
public static void Main()
{
String str = ")))()";
Console.WriteLine(balancedBrackets(str));
}
}
// This code is contributed by ihritik
Javascript
<script>
// JavaScript implementation of the approach
// Function to return balancedBrackets string
function balancedBrackets(str) {
// Initializing dep to 0
var dep = 0;
// Stores maximum negative depth
var minDep = 0;
for (var i = 0; i < str.length; i++) {
if (str[i] === "(") dep++;
else dep--;
// if dep is less than minDep
if (minDep > dep) minDep = dep;
}
// if minDep is less than 0 then there
// is need to add '(' at the front
if (minDep < 0) {
for (var i = 0; i < Math.abs(minDep); i++) str = "(" + str;
}
// Reinitializing to check the updated string
dep = 0;
for (var i = 0; i < str.length; i++) {
if (str[i] === "(") dep++;
else dep--;
}
// if dep is not 0 then there
// is need to add ')' at the back
if (dep !== 0) {
for (var i = 0; i < dep; i++) str = str + ")";
}
return str;
}
// Driver code
var str = ")))()";
document.write(balancedBrackets(str));
</script>
Producción
((()))()
Complejidad temporal: O(N)
Espacio auxiliar: O(N)